More bounds on the diameters of convex polytopes

Bremner D, Deza A, Hua W, Schewe L (2013)


Publication Status: Published

Publication Type: Journal article, Original article

Publication year: 2013

Journal

Publisher: Taylor & Francis: STM, Behavioural Science and Public Health Titles / Taylor & Francis

Book Volume: 28

Pages Range: 442-450

Journal Issue: 3

DOI: 10.1080/10556788.2012.668906

Abstract

Let Δ(d, n) be the maximum possible diameter of the vertex-edge graph over all d-dimensional polytopes defined by n inequalities. The Hirsch bound holds for particular n and d if Δ(d, n)≤n-d. Francisco Santos recently resolved a question open for more than five decades by showing that Δ(d, 2d)≥d+1 for d=43; the dimension was then lowered to 20 by Matschke, Santos and Weibel. This progress has stimulated interest in related questions. The existence of a polynomial upper bound for Δ(d, n) is still an open question, the best bound being the quasi-polynomial one due to Kalai and Kleitman in 1992. Another natural question is for how large n and d the Hirsch bound holds. Goodey showed in 1972 that Δ(4, 10)=5 and Δ(5, 11)=6, and more recently, Bremner and Schewe showed that Δ(4, 11)=Δ(6, 12)=6. Here, we show that Δ(4, 12)=Δ(5, 12)=7. © 2013 Copyright Taylor and Francis Group, LLC.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Bremner, D., Deza, A., Hua, W., & Schewe, L. (2013). More bounds on the diameters of convex polytopes. Optimization Methods & Software, 28(3), 442-450. https://dx.doi.org/10.1080/10556788.2012.668906

MLA:

Bremner, David, et al. "More bounds on the diameters of convex polytopes." Optimization Methods & Software 28.3 (2013): 442-450.

BibTeX: Download