Distances to lattice points in knapsack polyhedra

DOI10.1007/s10107-019-01392-1zbMath1445.90059arXiv1805.04592OpenAlexW2962994902MaRDI QIDQ2191767

Martin Henk, Timm Oertel, Iskander M. Aliev

Publication date: 26 June 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Integer programming (90C10) Lattice packing and covering (number-theoretic aspects) (11H31)

Related Items

Tightness of sensitivity and proximity bounds for integer linear programs, Proximity in concave integer quadratic programming, Improving the Cook et al. proximity bound given integral valued constraints, A colorful Steinitz lemma with application to block-structured integer programs, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, The Distributions of Functions Related to Parametric Integer Optimization, Distance-Sparsity Transference for Vertices of Corner Polyhedra, Proximity bounds for random integer programs, On Proximity for k-Regular Mixed-Integer Linear Optimization, Proximity bounds for random integer programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing additive integrality gaps
• Expected Frobenius numbers
• An optimal lower bound for the Frobenius problem
• Integer matrices, sublattices of \(\mathbb Z^m\), and Frobenius numbers
• On Lovász' lattice reduction and the nearest lattice point problem
• Lattice translates of a polytope and the Frobenius problem
• Geometric algorithms and combinatorial optimization
• On the lattice programming gap of the group problems
• Integrality gaps of integer knapsack problems
• Diameters of random circulant graphs
• Computing the integer programming gap
• On the limit distribution of Frobenius numbers
• Parametric Integer Programming in Fixed Dimension
• Sensitivity theorems in integer linear programming
• The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case
• Convex and Discrete Geometry
• Sur la densité des réseaux de domaines convexes
• On a Problem of Partitions