On Sub-determinants and the Diameter of Polyhedra
Bonifas, Nicolas; Di Summa, Marco; Eisenbrand, Friedrich; Haehnle, Nicolai; Niemeier, Martin
2014

Files

Abstract

We derive a new upper bound on the diameter of a polyhedron , where . The bound is polynomial in and the largest absolute value of a sub-determinant of , denoted by . More precisely, we show that the diameter of is bounded by . If is bounded, then we show that the diameter of is at most . For the special case in which is a totally unimodular matrix, the bounds are and respectively. This improves over the previous best bound of due to Dyer and Frieze (Math Program 64:1-16, 1994).

Details

Title On Sub-determinants and the Diameter of Polyhedra
Author(s) Bonifas, Nicolas ; Di Summa, Marco ; Eisenbrand, Friedrich ; Haehnle, Nicolai ; Niemeier, Martin
Published in Discrete & Computational Geometry
Pagination 14
Volume 52
Issue 1
Pages 102-115
Date 2014
Publisher New York, Springer
ISSN 0179-5376
Keywords
Note National Licences
DOI https://doi.org/10.1007/s00454-014-9601-x
Other identifier(s) View record in Web of Science
Laboratories DISOPT
Record Appears in Scientific production and competences > SB - School of Basic Sciences > MATH - Institute of Mathematics > DISOPT - Chair of Discrete Optimization
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date 2014-08-29

PDF