Distance-sparsity transference for vertices of corner polyhedra

DOI10.1137/20M1353228MaRDI QIDQ5147026zbMATH OpenOpenAlexFDO

Authors Marcel Celaya, Martin Henk, A. Williams, Iskander Aliev

Publication date 2 February 2021

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

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

zbMATH Keywords

corner polyhedrainteger prgrammingknapsack polytopeproximitysparsity

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Integer programming (90C10) Combinatorial optimization (90C27)

Abstract: We obtain a transference bound for vertices of corner polyhedra that connects two well-established areas of research: proximity and sparsity of solutions to integer programs. In the knapsack scenario, it gives an exponential (in the size of support of a solution) improvement on previously known proximity estimates. In addition, for general integer linear programs we obtain a resembling result that connects the minimum absolute nonzero entry of an optimal solution with the size of its support.

Recommendations

• Improving proximity bounds using sparsity
• Distances to lattice points in knapsack polyhedra
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Approximating polyhedra with sparse inequalities
• scientific article; zbMATH DE number 6850361

Cites work

• A survey of compressed sensing
• An integer analogue of Carathéodory's theorem
• Asymptotic geometric analysis. I
• Carathéodory bounds for integer cones
• Decoding by Linear Programming
• Diophantine approximations and diophantine equations
• Distances to lattice points in knapsack polyhedra
• scientific article; zbMATH DE number 6850361 (Why is no real title available?)
• Improving proximity bounds using sparsity
• On Siegel's lemma
• Optimizing sparsity over lattices and semigroups
• Sensitivity theorems in integer linear programming
• Some polyhedra related to combinatorial problems
• Sparse Solutions of Linear Diophantine Equations
• The structure of group relaxations
• The support of integer optimal solutions

Cited in

(7)

• Vertex fusion under distance constraints
• Improving the Cook et al. proximity bound given integral valued constraints
• Improving proximity bounds using sparsity
• The support of integer optimal solutions
• On -modular integer linear problems in the canonical form and equivalent problems
• Sparsity and integrality gap transference bounds for integer programs
• Sparsity and proximity transference in integer programming

This page was built for publication: Distance-sparsity transference for vertices of corner polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5147026)