×

The diameters of network-flow polytopes satisfy the Hirsch conjecture. (English) Zbl 1406.52023

The authors present a final solution to the problem of finding the exact bound on the diameter of a network-flow polytope. Their main result states that the diameters of all network-flow polytopes satisfy the Hirsch conjecture and there are network-flow polytopes, for which the Hirsch bound is tight. In particular, the diameter of a network with \(n\) nodes and \(m\) arcs does not exceed the linear bound \(m+n-1\). To prove this result, the authors show first that the diameter of an \(N_{1}\times N_{2}\)-transportation polytope is bounded above by \(N_{1}+N_{2}-1-\mu\), where \(\mu\) is the number of critical pairs of the transportation polytope. Then it is shown that the truth of the Hirsch conjecture in case of \(N_{1}\times N_{2}\)-transportation polytopes and their faces imply the main result of this paper. An algorithm, which defines a walk from an initial tree to a final tree on the 1-skeleton of a non-degenerate transportation polytope is described. The walk is fully defined by the corresponding concrete finite sequence of trees, which has at most \(N_{1}+N_{2}-1-\mu\) steps.

MSC:

52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
90C05 Linear programming
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)

Software:

LPbook
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Balinski, ML, The Hirsch conjecture for dual transportation polyhedra, Math. Oper. Res., 9, 629-633, (1984) · Zbl 0555.90071 · doi:10.1287/moor.9.4.629
[2] Balinski, ML; Russakoff, A, On the assignment polytope, SIAM Rev., 16, 516-525, (1974) · Zbl 0269.90051 · doi:10.1137/1016083
[3] Bonifas, N; Summa, M; Eisenbrand, F; Hähnle, N; Niemeier, M, On sub-determinants and the diameter of polyhedra, Discrete Comput. Geom., 52, 102-115, (2014) · Zbl 1310.52013 · doi:10.1007/s00454-014-9601-x
[4] Borgwardt, S, On the diameter of partition polytopes and vertex-disjoint cycle cover, Math. Program. Ser. A, 141, 1-20, (2013) · Zbl 1288.90049 · doi:10.1007/s10107-011-0504-9
[5] Borgwardt, S. De Loera, J.A., Finhold E., Miller, J.: The hierarchy of circuit diameters and transportation polytopes. Discrete Appl. Math. (2015). doi:10.1016/j.dam.2015.10.017 · Zbl 1383.05072
[6] Brightwell, G; Heuvel, J; Stougie, L, A linear bound on the diameter of the transportation polytope, Combinatorica, 26, 133-139, (2006) · Zbl 1150.90008 · doi:10.1007/s00493-006-0010-5
[7] Dantzig, G.: Linear Programming and Extensions. Princeton Univ Press, Princeton (1963) · Zbl 0108.33103 · doi:10.1515/9781400884179
[8] Loera, JA, New insights into the complexity and geometry of linear optimization, Optima Newsl. Math. Program. Soc., 87, 1-13, (2011)
[9] De Loera J.A., Kim, E.D.: Combinatorics and geometry of transportation polytopes: an update. In: Discrete Geometry and Algebraic Combinatorics, Volume 625 of Contemporary Mathematics, pp. 37-76. American Math. Society (2014) · Zbl 1360.90169
[10] Loera, JA; Kim, ED; Onn, S; Santos, F, Graphs of transportation polytopes, J. Comb. Theory Ser. A, 116, 1306-1325, (2009) · Zbl 1229.05190 · doi:10.1016/j.jcta.2009.03.010
[11] Pia, A; Michini, C, On the diameter of lattice polytopes, Discrete Comput. Geom., 55, 681-687, (2016) · Zbl 1342.52014 · doi:10.1007/s00454-016-9762-x
[12] Deza, A., Manoussakis, G. Onn, S.: Euler polytopes and convex matroid optimization. AdvOL-Report no. 2015/15 (2015)
[13] Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton Univ Press, Princeton (1962) · Zbl 0106.34802
[14] Fritzsche, K; Holt, FB, More polytopes meeting the conjectured Hirsch bound, Discrete Math., 205, 77-84, (1999) · Zbl 0944.52004 · doi:10.1016/S0012-365X(99)00017-5
[15] Greenberg, HJ, Diagnosing infeasibility in MIN-cost network flow problems part I: dual infeasibility, IMA J. Math. Manag., 1, 99-109, (1987) · Zbl 0677.90029 · doi:10.1093/imaman/1.2.99
[16] Holt, FB; Klee, V, Many polytopes meeting the conjectured Hirsch bound, Discrete Comput. Geom., 20, 1-17, (1998) · Zbl 0926.52013 · doi:10.1007/PL00009372
[17] Kim, ED; Santos, F, An update on the Hirsch conjecture, Jahresbericht der Deutschen Mathematiker-Vereinigung, 112, 73-98, (2010) · Zbl 1252.05052 · doi:10.1365/s13291-010-0001-8
[18] Klee, V; Walkup, DW, The \(d\)-step conjecture for polyhedra of dimension \(d <\) 6, Acta Math., 117, 53-78, (1967) · Zbl 0163.16801 · doi:10.1007/BF02395040
[19] Klee, V., Witzgall, C.: Facets and vertices of transportation polyhedra. Mathematics of the decision science, part 1. In: Lectures in Applied Mathematics, vol. 11, pp. 257-282 (1968)
[20] Naddef, D, The Hirsch conjecture is true for (0,1)-polytopes, Math. Program., 45, 109-110, (1989) · Zbl 0684.90071 · doi:10.1007/BF01589099
[21] Orlin, JB, A polynomial time primal network simplex algorithm for minimum cost flows, Math. Program., 78, 109-129, (1997) · Zbl 0888.90058 · doi:10.1007/BF02614365
[22] Pak, I, Four questions on Birkhoff polytope, Ann. Comb., 4, 83-90, (2000) · Zbl 0974.52010 · doi:10.1007/PL00001277
[23] Santos, F, A counterexample to the Hirsch conjecture, Ann. Math., 176, 383-412, (2012) · Zbl 1252.52007 · doi:10.4007/annals.2012.176.1.7
[24] Schrijver, A.: Combinatorial Optimization—Polyhedra and Efficiency. Springer, Berlin (2003) · Zbl 1041.90001
[25] Vanderbei, R.J.: Linear Programming: Foundations and Extensions. International Series in Operations Research and Management Science. Kluwer Academic, Boston (2001) · Zbl 1043.90002 · doi:10.1007/978-1-4757-5662-3
[26] Yemelichev, V.A., Kovalëv, M.M., Kravtsov, M.K.: Polytopes, Graphs and Optimisation. Cambridge University Press, Cambridge (1984)
[27] Zadeh, N, A bad network problem for the simplex method and other minimum cost flow algorithms, Math. Program., 5, 255-266, (1973) · Zbl 0287.90030 · doi:10.1007/BF01580132
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.