On the dominant of the s-t-cut polytope
Please always quote using this URN:urn:nbn:de:0296-matheon-5839
- The natural linear programming formulation of the maximum s-t-flow problem in path variables has a dual linear program whose underlying polyhedron is the dominant of the s-t-cut polytope. We present a complete characterization of this polytope with respect to vertices, facets, and adjacency.
Author: | Martin Skutella, Alexia Weber |
---|---|
URN: | urn:nbn:de:0296-matheon-5839 |
Referee: | Andreas Bley |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2009/07/21 |
Release Date: | 2009/07/20 |
Tag: | |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C05 Linear programming |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27] | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut | |
Preprint Number: | 612 |