betaFeedback

WorksMathematics

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

Abstract

In this paper, we prove that the decision version of weighted maximin dispersion over the unit ℓ1\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 ℓ1\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.

Paper details

vlnc:W_zpu8mbhb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…