Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. On Sub-determinants and the Diameter of Polyhedra
 
research article

On Sub-determinants and the Diameter of Polyhedra

Bonifas, Nicolas  
•
Di Summa, Marco  
•
Eisenbrand, Friedrich  
Show more
2014
Discrete & Computational Geometry

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

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

454_2014_Article_9601.pdf

Type

Publisher's Version

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

Size

263.71 KB

Format

Adobe PDF

Checksum (MD5)

cb6f62842f656f33db8ca455ecf5c32b

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés