Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

The diameters of network-flow polytopes satisfy the Hirsch conjecture

: Borgwardt, Steffen; Loera, Jesús A. de; Finhold, Elisabeth


Mathematical programming. Series A 171 (2018), Nr.1-2, S.283-309
ISSN: 0025-5610 (Print)
ISSN: 1436-4646 (Online)
Fraunhofer ITWM ()

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.