Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes. (English) Zbl 1311.52011
Summary: This paper features two main contributions. On the one hand, it gives an impressive survey on the progress on the diameter problem, including the breakthrough of the author [ibid. 21, No. 3, 426–460 (2013; Zbl 1280.52011)] with his disproof of the Hirsch conjecture among many other recent results. On the other hand, it features new results (exponential lower bounds) on the diameter of simplicial complexes and re-interprets the recent activities of the polymath 3 project that has been coordinated by Gil Kalai.
MSC:
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 90C05 | Linear programming |
| 05E45 | Combinatorial aspects of simplicial complexes |
Citations:
Zbl 1280.52011References:
| [1] | Balinski ML (1984) The Hirsch conjecture for dual transportation polyhedra. Math Oper Res 9(4):629–633 · Zbl 0555.90071 · doi:10.1287/moor.9.4.629 |
| [2] | Barnette D (1974) An upper bound for the diameter of a polytope. Discrete Math 10:9–13 · Zbl 0294.52007 · doi:10.1016/0012-365X(74)90016-8 |
| [3] | Bonifas N, Di Summa M, Eisenbrand F, Hähnle N, Niemeier M (2012) On sub-determinants and the diameter of polyhedra. In: Proceedings of the 28th annual ACM symposium on computational geometry, SoCG’12, pp 357–362 · Zbl 1293.52008 |
| [4] | Brightwell G, van den Heuvel J, Stougie L (2006) A linear bound on the diameter of the transportation polytope. Combinatorica 26(2):133–139 · Zbl 1150.90008 · doi:10.1007/s00493-006-0010-5 |
| [5] | Dyer M, Frieze A (1994) Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math Program, Ser A 64(1):1–16 · Zbl 0820.90066 · doi:10.1007/BF01582563 |
| [6] | De Loera JA, Kim ED, Onn S, Santos F (2009) Graphs of transportation polytopes. J Comb Theory, Ser A 116(8):1306–1325 · Zbl 1229.05190 · doi:10.1016/j.jcta.2009.03.010 |
| [7] | Eisenbrand F, Hähnle N, Razborov A, RothvoßT (2010) Diameter of polyhedra: Limits of abstraction. Math Oper Res 35(4):786–794 · Zbl 1226.52004 · doi:10.1287/moor.1100.0470 |
| [8] | Kalai G, Kleitman DJ (1992) A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull Am Math Soc 26(2):315–316 · Zbl 0751.52006 · doi:10.1090/S0273-0979-1992-00285-9 |
| [9] | Klee V, Walkup DW (1967) The d-step conjecture for polyhedra of dimension d<6. Acta Math 133:53–78 · Zbl 0163.16801 · doi:10.1007/BF02395040 |
| [10] | Larman DG (1970) Paths of polytopes. Proc Lond Math Soc 3(20):161–178 · Zbl 0199.59301 · doi:10.1112/plms/s3-20.1.161 |
| [11] | Naddef D (1989) The Hirsch conjecture is true for (0,1)-polytopes. Math Program 45:109–110 · Zbl 0684.90071 · doi:10.1007/BF01589099 |
| [12] | Orlin JB (1997) A polynomial time primal network simplex algorithm for minimum cost flows. Math Program, Ser B 78(2):109–129. Network optimization: algorithms and applications (San Miniato, 1993) |
| [13] | Santos F (2012) A counterexample to the Hirsch conjecture. Ann Math 176(1):383–412 · Zbl 1252.52007 · doi:10.4007/annals.2012.176.1.7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
