Proximity and Flatness Bounds for Linear Integer Optimization
METADATA ONLY
Loading...
Author / Producer
Date
2024-11
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
This paper deals with linear integer optimization. We develop a technique that can be applied to provide improved upper bounds for two important questions in linear integer optimization. Given an optimal vertex solution for the linear relaxation, how far away is the nearest optimal integer solution (if one exists; proximity bounds)? If a polyhedron contains no integer point, what is the smallest number of integer parallel hyperplanes defined by an integral, nonzero, normal vector that intersect the polyhedron (flatness bounds)? This paper presents a link between these two questions by refining a proof technique that has been recently introduced by the authors. A key technical lemma underlying our technique concerns the areas of certain convex polygons in the plane; if a polygon K ⊆ R2 satisfies τK ⊆ K◦, where τ denotes 90◦ counterclockwise rotation and K◦ denotes the polar of K, then the area of K◦ is at least three.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
49 (4)
Pages / Article No.
2446 - 2467
Publisher
INFORMS
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03873 - Weismantel, Robert / Weismantel, Robert