Proximity and Flatness Bounds for Linear Integer Optimization
成果类型：
Article
署名作者：
Celaya, Marcel; Kuhlmann, Stefan; Paat, Joseph; Weismantel, Robert
署名单位：
Cardiff University; Technical University of Berlin; University of British Columbia
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2022.0335
发表日期：
2024
页码：
2446-2467
关键词：
摘要：
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 subset of R2 satisfies tau K subset of K degrees, where tau denotes 90 degrees counterclockwise rotation and K degrees denotes the polar of K, then the area of K degrees is at least three.
来源URL：