Optimization Online


Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture

Edward D. Kim(E.D.H.Kim***at***tudelft.nl)

Abstract: We introduce a new combinatorial abstraction for the graphs of polyhedra. The new abstraction is a flexible framework defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. One particular variant has a diameter which satisfies the best known upper bound on the diameters of polyhedra. Another variant has superlinear asymptotic diameter, and together with some combinatorial operations, gives a concrete approach for disproving the Linear Hirsch Conjecture.

Keywords: convex polytopes, Hirsch Conjecture, linear programming

Category 1: Combinatorial Optimization (Polyhedra )

Citation: submitted

Download: [PDF]

Entry Submitted: 03/17/2011
Entry Accepted: 03/17/2011
Entry Last Modified: 03/17/2011

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 Programming Society