Maximin Dispersion over Simple Polyhedral Domains: Strong NP-Completeness and Exact Algorithms
Source: arxiv.org/abs/2611.22578
In this paper, we prove that the decision version of weighted maximin dispersion over the unit $\ell_1$-ball with rational sites and positive rational weights is strongly NP-complete. The same holds for unweighted dispersion over full-dimensional integer simplices when the sites are exactly their vertices. Both reductions from Exact Cover by 3-Sets rely on a shared quadratic rigidity argument. We also give exact algorithms that run in polynomial time for every fixed dimension. For the simplex problem, a Voronoi decomposition yields rational optimal solutions. For the weighted $\ell_1$-ball…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.22578
curl -X POST /api/v1/records/arxiv/2611.22578/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.22578/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'