Diameter of Polyhedra: Limits of Abstraction

References

• Adler I. Lower bounds for maximum diameters of polytopes. Math. Programming Stud. (1974) 1:11–19Crossref, Google Scholar
• Adler I., Dantzig G. B. Maximum diameter of abstract polytopes. Math. Programming Stud. (1974) 1:20–40Crossref, Google Scholar
• Adler I., Dantzig G., Murty K. Existence of A-avoiding paths in abstract polytopes. Math. Programming Stud. (1974) 1:41–42Crossref, Google Scholar
• Alon N., Spencer J.The Probabilistic Method (2008) 3rd ed.(Wiley-Interscience, New York) Crossref, Google Scholar
• Bremner D., Schewe L. Edge-graph diameter bounds for convex polytopes with few facets. (2009) . arXiv:0809.0915v3 [math.CO]Google Scholar
• Erdős P., Hanani H. On a limit theorem in combinatorial analysis. Publicationes Mathematicae Debrecen (1963) 10:10–13Google Scholar
• Gärtner B. A subexponential algorithm for abstract optimization problems. SIAM J. Comput. (1995) 24(5):1018–1035Crossref, Google Scholar
• Gärtner B. The random-facet simplex algorithm on combinatorial cubes. Random Structures Algorithms (2002) 20(3):353–381Crossref, Google Scholar
• Kalai G. A subexponential randomized simplex algorithm (extended abstract). Proc. 24th Ann. ACM Symposium Theory Comput. (1992) (ACM, New York) 475–482Crossref, Google Scholar
• Kalai G. Upper bounds for the diameter and height of graphs of convex polyhedra. Discrete Computational Geometry (1992) 8(1):363–372Crossref, Google Scholar
• Kalai G. Linear programming, the simplex algorithm and simple polytopes. Math. Programming (1997) 79(1–3):217–233Crossref, Google Scholar
• Kalai G., Kleitman D. J. A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Amer. Math. Soc. (1992) 26:315–316Crossref, Google Scholar
• Klee V., Kleinschmidt P. The d-step conjecture and its relatives. Math. Oper. Res. (1987) 12(4):718–755Link, Google Scholar
• Klee V., Walkup D. W. The d-step conjecture for polyhedra of dimension d < 6. Acta Mathematica (1967) 117(1):53–78Crossref, Google Scholar
• Larman D. G. Paths on polytopes. Proc. London Math. Soc. (1970) s3-20(1):161–178Crossref, Google Scholar
• Mani P., Walkup D. W. A 3-sphere counterexample to the Wv-path conjecture. Math. Oper. Res. (1980) 5(4):595–598Link, Google Scholar
• Matoušek J., Sharir M., Welzl E. A subexponential bound for linear programming. Algorithmica (1996) 16(4–5):498–516Crossref, Google Scholar
• Rödl V. On a packing and covering problem. Eur. J. Combinatorics (1985) 5:69–78Crossref, Google Scholar
• Santos F. A counterexample to the Hirsch conjecture. (2010) . arXiv:1006.2814v1 [math.CO]Google Scholar
• Schurr I., Szabó T. Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes. Discrete Computational Geometry (2004) 31(4):627–642Crossref, Google Scholar