2022/11/27 by Marcel Celaya, Stefan Kuhlmann, Celaya, Marcel +5 · 1 citation
Mathematics · Computer Science · #Advanced Optimization Algorithms Research #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2211.14941
We develop a technique that can be applied to provide improved upper bounds for two important questions in linear integer optimization. - Proximity bounds: Given an optimal vertex solution for the linear relaxation, how far away is the nearest optimal integer solution (if one exists)? - Flatness bounds: If a polyhedron contains no integer point, what is the smallest number of integer parallel hyperplanes defined by an integral, non-zero, normal vector that intersect the polyhedron? 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⊆ℝ2 satisfies τK ⊆ K∘, where τ denotes 90∘ counterclockwise rotation and K∘ denotes the polar of K, then the area of K∘ is at least 3.