Paperlane

no. 17 · Wednesday 18 November 2026

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

Linbin Li, Yong Xia and Zhuoyi Xu

math.OC

Abstract

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 problem, an orthant decomposition and a single-paraboloid lifting yield optimal solutions whose coordinates lie in a common real algebraic extension of degree at most two. In both cases, these solutions have polynomial encoding length and provide certificates for NP membership.

fields
Optimization and Control
pdf ↗ page arXiv:2611.22578 ↗