- Conference Paper
We refer to the distance between optimal solutions of integer programs and their linear relaxations as proximity. In 2018 Eisenbrand and Weismantel proved that proximity is independent of the dimension for programs in standard form. We improve their bounds using results on the sparsity of integer solutions. We first bound proximity in terms of the largest absolute value of any full-dimensional minor in the constraint matrix, and this bound is tight up to a polynomial factor in the number of constraints. We also give an improved bound in terms of the largest absolute entry in the constraint matrix, after efficiently transforming the program into an equivalent one. Our results are stated in terms of general sparsity bounds, so any new sparsity results immediately improve our work. Generalizations to mixed integer programs are also discussed. Show more
Book titleCombinatorial Optimization, 6th International Symposium, ISCO 2020, Montreal, QC, Canada, May 4–6, 2020, Revised Selected Papers
Journal / seriesLecture Notes in Computer Science
Pages / Article No.
SubjectProximity; Sparsity; Mixed integer programming
Organisational unit03873 - Weismantel, Robert / Weismantel, Robert
NotesConference lecture held on May 4, 2020. The conference is postponed due to the Corona virus (COVID-19).
MoreShow all metadata