Loading...
research article
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).
Loading...
Name
454_2014_Article_9601.pdf
Type
Publisher's version
Access type
openaccess
Size
263.71 KB
Format
Adobe PDF
Checksum (MD5)
cb6f62842f656f33db8ca455ecf5c32b