Diameter of polyhedra: limits of abstraction

ABSTRACT

We investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Although this abstraction is simpler than other abstractions that were previously studied in the literature, the best upper bounds on the diameter of polyhedra continue to hold here. On the other hand, we show that this abstraction has its limits by providing a superlinear lower bound.

REFERENCES

• 1: Ilan Adler. Lower bounds for maximum diameters of polytopes. Math. Programming Stud., pages 11--19, 1974. Pivoting and extensions.
• 2: Ilan Adler, George Dantzig, and Katta Murty. Existence of A-avoiding paths in abstract polytopes. Math. Programming Stud., (1):41--42, 1974. Pivoting and extensions.
• 3: Ilan Adler and George B. Dantzig. Maximum diameter of abstract polytopes. Mathematical Programming Study, (1):20--40, 1974. Pivoting and extensions.
• 4: Reinhard Diestel. Graph theory. Springer-Verlag, New York, 2 edition, 2000.
• 5: Paul Erdos and Haim Hanani. On a limit theorem in combinatorial analysis. Publ. Math. Debrecen, 10:10--13, 1963.
• 6: Bernd Gartner, A Subexponential Algorithm for Abstract Optimization Problems, SIAM Journal on Computing, v.24 n.5, p.1018-1035, Oct. 1995 [doi>10.1137/S0097539793250287]
• 7: Bernd Gärtner, The random facet simplex algorithm on combinatorial cubes, Random Structures & Algorithms, v.20 n.3, p.353-381, May 2002 [doi>10.1002/rsa.10034]
• 8: Gil Kalai, A subexponential randomized simplex algorithm (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.475-482, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129759]
• 9: Gil Kalai. Upper bounds for the diameter and height of graphs of convex polyhedra. Discrete & Computational Geometry, 8:363--372, 1992.
• 10: Gil Kalai, Linear programming, the simplex algorithm and simple polytopes, Mathematical Programming: Series A and B, v.79 n.1-3, p.217-233, Oct. 1, 1997 [doi>10.1007/BF02614318]
• 11: Gil Kalai and Daniel J. Kleitman. A quasi-polynomial bound for the diameter of graphs of polyhedra. Bulletin of the American Mathematical Society, 26:315--316, 1992.
• 12: Victor Klee , Peter Kleinschmidt, The d-step conjecture and its relatives, Mathematics of Operations Research, v.12 n.4, p.718-755, Nov. 1987 [doi>10.1287/moor.12.4.718]
• 13: Victor Klee and David W. Walkup. The d-step conjecture for polyhedra of dimension d < 6. Acta Math. 133, pages 53--78, 1967.
• 14: David G. Larman. Paths on polytopes. Proceedings London Math. Soc., pages 161--178, 1970.
• 15: Peter Mani and David W. Walkup. A 3-sphere counterexample to the Wv-path conjecture. Math. Oper. Res., 5(4):595--598, 1980.
• 16: Jiri Matousek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. Algorithmica, 16(4/5):498--516, October/November 1996.
• 17: Vojtech Rodl. On a packing and covering problem. European Journal of Combinatorics, (5):69--78, 1985.
• 18: Ingo Schurr , Tibor Szabó, Finding the Sink Takes Some Time: An Almost Quadratic Lower Bound for Finding the Sink of Unique Sink Oriented Cubes, Discrete & Computational Geometry, v.31 n.4, p.627-642, March 2004 [doi>10.1007/s00454-003-0813-8]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Theory

Keywords:
convex geometry, disjoint coverings, hirsch conjecture, polyhedra