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

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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-17
DOI
https://doi.org/10.48550/arxiv.2611.22578
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

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

Linbin Li, Zhuoyi Xu, Yong Xia
arXiv (Cornell University)
Complexity and Algorithms in Graphs
preprint

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

Linbin Li, Zhuoyi Xu, Yong Xia
preprint en

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.

arXiv (Cornell University)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon