Edges versus circuits: a hierarchy of diameters in polyhedra. (English) Zbl 1386.52008
Summary: The study of the graph diameter of polytopes is a classical open problem in polyhedral geometry and the theory of linear optimization. In this paper we continue the investigation initiated in [the first author et al., SIAM J. Discrete Math. 29, No. 1, 113–121 (2015; Zbl 1335.90058)] by introducing a vast hierarchy of generalizations to the notion of graph diameter. This hierarchy provides some interesting lower bounds for the usual graph diameter. After explaining the structure of the hierarchy and discussing these bounds, we focus on clearly explaining the differences and similarities among the many diameter notions of our hierarchy. Finally, we fully characterize the hierarchy in dimension two. It collapses into fewer categories, for which we exhibit the ranges of values that can be realized as diameters.
MSC:
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 52B55 | Computational aspects related to convexity |
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
| 52C40 | Oriented matroids in discrete geometry |
| 52C45 | Combinatorial complexity of geometric structures |
| 90C05 | Linear programming |
| 90C49 | Extreme-point and pivoting methods |
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
Citations:
Zbl 1335.90058References:
| [1] | A. Bachem, W. Kern, Linear programming duality. Springer 1992. MR1230380 Zbl 0757.90050; Bachem, A.; Kern, W., Linear programming duality (1992) · Zbl 0757.90050 |
| [2] | A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G. M. Ziegler, Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press 1999. MR1744046 Zbl 0944.52006; Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; Ziegler, G. M., Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications (1999) · Zbl 0944.52006 |
| [3] | R. G. Bland, New finite pivoting rules for the simplex method. Math. Oper. Res. 2 (1977), 103-107. MR0459599 Zbl 0408.90050; Bland, R. G., New finite pivoting rules for the simplex method, Math. Oper. Res, 2, 103-107 (1977) · Zbl 0408.90050 |
| [4] | S. Borgwardt, J. A. De Loera, E. Finhold, J. Miller, The hierarchy of circuit diameters and transportation polytopes. Discrete Applied Mathematics (2015).; Borgwardt, S.; De Loera, J. A.; Finhold, E.; Miller, J., The hierarchy of circuit diameters and transportation polytopes, Discrete Applied Mathematics (2015) · Zbl 1383.05072 · doi:10.1016/j.dam.2015.10.017 |
| [5] | S. Borgwardt, E. Finhold, R. Hemmecke, On the circuit diameter of dual transportation polyhedra. SIAM J. Discrete Math. 29 (2015), 113-121. MR3300405 Zbl 06514452; Borgwardt, S.; Finhold, E.; Hemmecke, R., On the circuit diameter of dual transportation polyhedra, SIAM J. Discrete Math, 29, 113-121 (2015) · Zbl 1335.90058 |
| [6] | K. Fukuda, T. Terlaky, Criss-cross methods: a fresh view on pivot algorithms. Math. Programming79 (1997), 369-395. MR1464775 Zbl 0887.90113; Fukuda, K.; Terlaky, T., Criss-cross methods: a fresh view on pivot algorithms, Math. Programming, 79, 369-395 (1997) · Zbl 0887.90113 |
| [7] | R. Hemmecke, S. Onn, R. Weismantel, A polynomial oracle-time algorithm for convex integer minimization. Math. Program. 126 (2011), 97-117. MR2764341 Zbl 1228.90055; Hemmecke, R.; Onn, S.; Weismantel, R., A polynomial oracle-time algorithm for convex integer minimization, Math. Program, 126, 97-117 (2011) · Zbl 1228.90055 |
| [8] | E. D. Kim, F. Santos, An update on the Hirsch conjecture. Jahresber. Dtsch. Math.-Ver. 112 (2010), 73-98. MR2681516 Zbl 1252.05052; Kim, E. D.; Santos, F., An update on the Hirsch conjecture, Jahresber. Dtsch. Math.-Ver, 112, 73-98 (2010) · Zbl 1252.05052 |
| [9] | R. T. Rockafellar, The elementary vectors of a subspace of \(R^N\). In: Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967), 104-127, Univ. North Carolina Press, Chapel Hill, N.C. 1969.; Rockafellar, R. T., The elementary vectors of a subspace of \(R^N, 104-127 (1969)\) · Zbl 0229.90019 |
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.
