The diameters of network-flow polytopes satisfy the Hirsch conjecture

• 成果类型: Article
• 署名作者: Borgwardt, S.; De Loera, J. A.; Finhold, E.
• 署名单位: University of Colorado System; University of Colorado Denver; University of California System; University of California Davis; Fraunhofer Gesellschaft
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1176-x
• 发表日期: 2018
• 页码: 283-309
• 关键词: polyhedra

摘要

We solve a problem in the combinatorics of polyhedra motivated by the network simplex method. We show that the Hirsch conjecture holds for the diameter of the graphs of all network-flow polytopes, in particular the diameter of a network-flow polytope for a network with n nodes and m arcs is never more than m + n - 1. A key step to prove this is to show the same result for classical transportation polytopes.