×

zbMATH — the first resource for mathematics

On the circuit diameter of some combinatorial polytopes. (English) Zbl 1416.52006
The combinatorial diameter of a polytope \(P\) on \(n\) vertices is the maximum value of a shortest path in the \(1\)-skeleton of \(P\) between two vertices in \(P\). The combinatorial diameter is linked to longstanding open questions about the existence of a pivoting rule that yields a polynomial running time for the Simplex Method. The circuit diameter of a polytope \(P\) is the maximum value of a shortest path in the \(1\)-skeleton of \(P\) between two vertices of \(P\) that uses potential edge direction of \(P\), that is if \(P = \{\tilde{x}\in {\mathbb{R}}^n : A\tilde{x} = \tilde{b}, \ \ B\tilde{x}\leq \tilde{d}\}\) where \(A\) and \(B\) are rational matrices, and \(\tilde{b}\) and \(\tilde{d}\) are rational vectors, then the circuits of \(P\) are the set of potential edge directions that can arise by varying \(\tilde{b}\) and \(\tilde{d}\).
In this paper, the authors study the circuit diameter of the matching polytope, the perfect matching polytope, the Traveling Salesman (TSP) polytope, and the fractional stable set polytope. An exact characterization of the circuit diameter of the matching polytope is given, in particular is is shown to be equal to \(2\) for \(n\geq 7\). The circuit diameter of the perfect matching polytope on \(n\) vertices is shown to be equal to \(1\) for \(n\neq 8\) and equal to \(2\) for \(n=8\). An exact characterization of the circuit diameter of the TSP polytope is given. It is shown to be equal to \(1\) for \(n\neq 5\) and equal to \(2\) for \(n=5\). Finally, a complete characterization of the circuit diameter of the fractional stable set polytope is presented. It is shown to be essentially upper bounded by the diameter of \(P\), which is often significantly smaller than \(n\), the number of vertices of \(P\).

MSC:
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. L. Balinski, On maximum matching, minimum covering and their connections, Proceedings of the Princeton Symposium on Mathematical Programming, Princeton University Press, Princeton, NJ, pp. 303–312.
[2] M. L. Balinski, The Hirsch conjecture for dual transportation polyhedra, Math. Oper. Res., 9 (1984), pp. 629–633. · Zbl 0555.90071
[3] M. L. Balinski and A. Russakoff, On the assignment polytope, SIAM Rev., 16 (1974), pp. 516–525, . · Zbl 0269.90051
[4] S. Borgwardt, J. A. De Loera, and E. Finhold, Edges versus circuits: A hierarchy of diameters in polyhedra, Adv. Geom., 16 (2016), pp. 511–530. · Zbl 1386.52008
[5] S. Borgwardt, J. A. De Loera, and E. Finhold, The diameters of network-flow polytopes satisfy the Hirsch conjecture, Math. Program., 171 (2018), pp. 283–309, . · Zbl 1406.52023
[6] S. Borgwardt, E. Finhold, and R. Hemmecke, On the circuit diameter of dual transportation polyhedra, SIAM J. Discrete Math., (2015), pp. 113–121. · Zbl 1335.90058
[7] S. Borgwardt, E. Finhold, and R. Hemmecke, Quadratic diameter bounds for dual network flow polyhedra, Math. Program., 159 (2016), pp. 237–251, . · Zbl 1353.90083
[8] S. Borgwardt, J. D. Loera, E. Finhold, and J. Miller, The hierarchy of circuit diameters and transportation polytopes, Discrete Appl. Math., 240 (2018), pp. 8–24, . · Zbl 1383.05072
[9] S. Borgwardt, T. Stephen, and T. Yusun, On the circuit diameter conjecture, Discrete Comput. Geom., 60 (2018), pp. 558–587, . · Zbl 1401.52019
[10] G. Brightwell, J. van den Heuvel, and L. Stougie, A linear bound on the diameter of the transportation polytope, Combinatorica, 26 (2006), pp. 133–139, . · Zbl 1150.90008
[11] M. Campêlo and G. Cornuéjols, Stable sets, corner polyhedra and the Chvátal closure, Oper. Res. Lett., 37 (2009), pp. 375–378, .
[12] V. Chvátal, On certain polytopes associated with graphs, J. Combin. Theory, Series B, 18 (1975), pp. 138–154, .
[13] G. Cornuéjols, C. Michini, and G. Nannicini, How tight is the corner relaxation? Insights gained from the stable set problem, Discrete Optim., 9 (2012), pp. 109–121, . · Zbl 1252.90052
[14] J. De Loera, R. Hemmecke, and J. Lee, On augmentation algorithms for linear and integer-linear programming: From Edmonds–Karp to Bland and beyond, SIAM J. Optim., 25 (2015), pp. 2494–2511, . · Zbl 1330.90053
[15] J. Edmonds, Maximum matching and a polyhedron with \(0,1\)-vertices, J. Res. Natl. Bur. Stand. B, 69B (1965), pp. 125–130. · Zbl 0141.21802
[16] E. Finhold, Circuit Diameters and Their Application to Transportation Problems, Ph.D. thesis, Technische Universität München, Munich, Germany, 2015.
[17] J. Fonlupt and D. Naddef, The Traveling Salesman problem in graphs with some excluded minors, Math. Program., 53 (1992), pp. 147–172. · Zbl 0780.05034
[18] M. Grötschel and M. Padberg, Polyhedral theory, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Norman Biggs, ed., John Wiley and Sons, New York, 1986, pp. 251–305.
[19] M. Grötschel and M. W. Padberg, On the symmetric Travelling Salesman problem. I. Inequalities, Math. Program., 16 (1979), pp. 265–280, . · Zbl 0413.90048
[20] R. Hemmecke, On the positive sum property and the computation of Graver test sets, Math. Program., 96 (2003), pp. 247–269. · Zbl 1059.90108
[21] V. Klee and D. W. Walkup, The d-step conjecture for polyhedra of dimension \(d<6\), Acta Mathematica, 117 (1967), pp. 53–78, . · Zbl 0163.16801
[22] C. Michini and A. Sassano, The Hirsch conjecture for the fractional stable set polytope, Math. Program., 147 (2014), pp. 309–330, . · Zbl 1297.90086
[23] M. W. Padberg and M. R. Rao, The Travelling Salesman problem and a class of polyhedra of diameter two, Math. Program., 7 (1974), pp. 32–45, . · Zbl 0318.90042
[24] F. Rispoli and S. Cosares, A bound of 4 for the diameter of the symmetric Traveling Salesman polytope, SIAM J. Discrete Math., 11 (1998), pp. 373–380, . · Zbl 0914.90258
[25] F. Santos, A counterexample to the Hirsch conjecture, Ann. Math., 176 (2012), pp. 383–412. · Zbl 1252.52007
[26] A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Springer, New York, 2003. · Zbl 1041.90001
[27] N. Sukegawa, Improving bounds on the diameter of a polyhedron in high dimensions, Discrete Math., 340 (2017), pp. 2134–2142, . · Zbl 1370.52019
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.