Optimization Online


Improvement of Kalai-Kleitman bound for the diameter of a polyhedron

Noriyoshi Sukegawa (sukegawa.n.aa***at***m.titech.ac.jp)
Tomonari Kitahara (kitahara.t.ab***at***m.titech.ac.jp)

Abstract: Recently, Todd got a new bound on the diameter of a polyhedron using an analysis due to Kalai and Kleitman in 1992. In this short note, we prove that the bound by Todd can further be improved. Although our bound is not valid when the dimension is 1 or 2, it is tight when the dimension is 3, and fits better for a high-dimensional polyhedron with a large number of facets.

Keywords: Polytopes, Diameter, Kalai and Kleitman bound

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Technical report, Tokyo Institute of Technology

Download: [PDF]

Entry Submitted: 10/20/2014
Entry Accepted: 10/20/2014
Entry Last Modified: 11/19/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society