Campus Event Calendar
Event Entry
What and Who
Diameter of the Transportation Polytope
Peter Korteweg
Eindhoven University of Technology
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 27 April 2005
13:30
30 Minutes
46.1 - MPII
024
Saarbrücken
Abstract
The diameter of a polyhedron is the maximum length of a shortest edge following path between vertices X and Y of the polyhedron. The existence of a polynomial bound on the maximum diameter is closely related to the existence of a polynomial time simplex algorithm for linear programming.
In 1957 Hirsch conjectured a linear upper bound on the maximum diameter of polyhedra. For bounded polyhedra (polytopes) the conjecture is still unsettled in the general case. We present constructive proofs of a linear upper- and lower bound on the maximum diameter of the transportation polytope. Our upper bound is a factor of 8 away from the conjectured Hirsch bound for this class of polytopes.
Most of the talk is based on Brightwell, Van den Heuvel, Stougie, "A linear bound on the diameter of the transportation polytope", Combinatorica (to appear).
Contact
Rene Sitters
--email hidden
passcode not visible
logged in users only
Rene Sitters, 04/18/2005 15:04
Rene Sitters, 03/01/2005 17:30
Rene Sitters, 03/01/2005 17:28 -- Created document.
Rene Sitters, 03/01/2005 17:30
Rene Sitters, 03/01/2005 17:28 -- Created document.