Distance-Sparsity Transference for Vertices of Corner Polyhedra

DOI10.1137/20M1353228zbMath1458.90475arXiv2007.00950OpenAlexW3121090231MaRDI QIDQ5147026

Martin Henk, Aled Williams, Marcel Celaya, Iskander M. 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

proximitysparsitycorner polyhedraknapsack polytopeinteger prgramming

Mathematics Subject Classification ID

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

Related Items

Improving the Cook et al. proximity bound given integral valued constraints, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems

Cites Work

• Unnamed Item
• Unnamed Item
• On Siegel's lemma
• An integer analogue of Carathéodory's theorem
• Diophantine approximations and diophantine equations
• Distances to lattice points in knapsack polyhedra
• Improving proximity bounds using sparsity
• Carathéodory bounds for integer cones
• Some polyhedra related to combinatorial problems
• A Survey of Compressed Sensing
• Decoding by Linear Programming
• Sensitivity theorems in integer linear programming
• The Support of Integer Optimal Solutions
• Optimizing Sparsity over Lattices and Semigroups
• Asymptotic Geometric Analysis, Part I
• Sparse Solutions of Linear Diophantine Equations