Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube

DOI10.1137/22m1489988zbMath1519.90170arXiv2204.05266OpenAlexW4378375458MaRDI QIDQ6155880

Robert Weismantel, Sebastian Pokutta, Christoph Hunkenschröder

Publication date: 7 June 2023

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2204.05266

zbMATH Keywords

polynomial time algorithmdiscrete optimizationconvex minimization

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial optimization (90C27) Convexity of real functions of several variables, generalizations (26B25)

Related Items

Optimizing low dimensional functions over the integers

Cites Work

• Unnamed Item
• A polynomial oracle-time algorithm for convex integer minimization
• Nonlinear discrete optimization. An algorithmic theory
• Convex integer maximization via Graver bases
• Value of the Steinitz constant
• Geometric algorithms and combinatorial optimization
• Convex combinatorial optimization
• Integer convex minimization by mixed integer linear optimization
• Constructing lattice-free gradient polyhedra in dimension two
• Convexity in cristallographical lattices
• Sensitivity theorems in integer linear programming
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• A Polyhedral Frobenius Theorem with Applications to Integer Optimization
• Convex separable optimization is not much harder than linear optimization