{"id":"arxiv/2609.15114","url":"https://arxiv.org/abs/2609.15114","tags":["math.OC"],"score":0,"title":"Integer Maximization over $\\ell_p$ Balls: Hardness and Exact Algorithms","domain":"math.OC","source":"arxiv","authors":["Cinar Ari","Robert Hildebrand"],"reviews":0,"subject":"math.OC","summary":"We study the problem of maximizing a linear function over the integer points of an origin-centered $\\ell_p$ ball, which we call \\BallIPp{p}. For every fixed integer $p\\ge2$, we prove that the decision problem over an $\\ell_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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}