Integer Maximization over ℓp Balls: Hardness and Exact Algorithms
Abstract
We study the problem of maximizing a linear function over the integer points of an origin-centered ℓp ball, which we call \BallIPp{p}. For every fixed integer p≥2, we prove that the decision problem over an ℓp-ball is NP-complete. We then focus on the Euclidean case and study how the difficulty of the problem depends on the numerical parameters of the instance. We give two complementary pseudo-polynomial exact algorithms. The first specializes a known radius-budget dynamic program; the same nonlinear-knapsack framework also applies to every fixed finite integer p. We then develop a complementary dynamic program over candidate objective values for the Euclidean case. The latter is polynomial in the encoding size of the radius and pseudo-polynomial in the magnitude of the cost coefficients. For a fixed objective value, feasibility can be formulated as a closest vector problem (CVP) instance. This connection gives an exact algorithm whose running time depends on the covering radius of that lattice. Conversely, we show that a rank-k Euclidean closest-vector instance in ambient dimension d reduces to the decision version of a Euclidean \BallIP{} instance in dimension d+k≤2d, transferring known bounds under the Exponential Time Hypothesis (ETH). Finally, we study dimension-dependent approaches based on proximity to the continuous optimizer and describe the fixed-level constructions that extend to ellipsoids.
Related
- On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization
- Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness
- Hardness of integer linear feasibility with cyclic support
- Demand Estimation with Unobserved Stockout Substitution: Exact Likelihood Maximization
- Funk Beta Balls: Exact Potentials and a Three-Phase Pyramid Diagram
BibTeX
@misc{ari2026integer,
title = {{Integer Maximization over $\ell_p$ Balls: Hardness and Exact Algorithms}},
author = {Cinar Ari and Robert Hildebrand},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15114},
eprint = {2609.15114},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15114},
}
RIS
TY - UNPB
TI - Integer Maximization over ℓ_p Balls: Hardness and Exact Algorithms
AU - Cinar Ari
AU - Robert Hildebrand
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15114
UR - https://arxiv.org/abs/2609.15114
AB - We study the problem of maximizing a linear function over the integer points of an origin-centered ℓ_p ball, which we call \BallIPp{p}. For every fixed integer p≥2, we prove that the decision problem over an ℓ_p-ball is NP-complete. We then focus on the Euclidean case and study how the difficulty of the problem depends on the numerical parameters of the instance. We give two complementary pseudo-polynomial exact algorithms. The first specializes a known radius-budget dynamic program; the same nonlinear-knapsack framework also applies to every fixed finite integer p. We then develop a complementary dynamic program over candidate objective values for the Euclidean case. The latter is polynomial in the encoding size of the radius and pseudo-polynomial in the magnitude of the cost coefficients. For a fixed objective value, feasibility can be formulated as a closest vector problem (CVP) instance. This connection gives an exact algorithm whose running time depends on the covering radius of that lattice. Conversely, we show that a rank-k Euclidean closest-vector instance in ambient dimension d reduces to the decision version of a Euclidean \BallIP{} instance in dimension d+k≤2d, transferring known bounds under the Exponential Time Hypothesis (ETH). Finally, we study dimension-dependent approaches based on proximity to the continuous optimizer and describe the fixed-level constructions that extend to ellipsoids.
ER -