Delphi.science

Maximin Dispersion over Simple Polyhedral Domains: Strong NP-Completeness and Exact Algorithms

Source: arxiv.org/abs/2611.22578

Linbin Li, Yong Xia, Zhuoyi Xu

arXivarxiv/2611.22578Nov 17, 2026math.OCscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'