On Sub-determinants and the Diameter of Polyhedra

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).


Published in:
Discrete & Computational Geometry, 52, 1, 102-115
Year:
2014
Publisher:
New York, Springer
ISSN:
0179-5376
Keywords:
Laboratories:




 Record created 2014-08-29, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)