Fraunhofer-Gesellschaft

Publica

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)
Englisch
Zeitschriftenaufsatz
Fraunhofer ITWM ()

Abstract
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.

: http://publica.fraunhofer.de/dokumente/N-477163.html