{"id":"arxiv/2611.22578","url":"https://arxiv.org/abs/2611.22578","tags":["math.OC"],"score":0,"title":"Maximin Dispersion over Simple Polyhedral Domains: Strong NP-Completeness and Exact Algorithms","domain":"math.OC","source":"arxiv","authors":["Linbin Li","Yong Xia","Zhuoyi Xu"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-17","reactions":{}}