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 |
