Name
Abstract | ||
|---|---|---|
Both the combinatorial and the circuit diameter of polyhedra are of interest to the theory of linear programming for their intimate connection to a best-case performance of linear programming algorithms. We study the diameters of dual network flow polyhedra associated to b-flows on directed graphs $$G=(V,E)$$G=(V,E) and prove quadratic upper bounds for both of them: the minimum of $$(|V|-1)\\cdot |E|$$(|V|-1)·|E| and $$\\frac{1}{6}|V|^3$$16|V|3 for the combinatorial diameter, and $$\\frac{|V|\\cdot (|V|-1)}{2}$$|V|·(|V|-1)2 for the circuit diameter. Previously, bounds on these diameters have only been known for bipartite graphs. The situation is much more involved for general graphs. In particular, we construct a family of dual network flow polyhedra with members that violate the circuit diameter bound for bipartite graphs by an arbitrary additive constant. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10107-015-0956-4 | Mathematical Programming: Series A and B |
Keywords | Field | DocType |
Combinatorial diameter, Circuit diameter, Hirsch conjecture, Edges, Circuits, Graver basis, Linear program, Integer program, 52B05, 90C05, 90C08, 90C10 | Flow network,Discrete mathematics,Combinatorics,Mathematical optimization,Graver basis,Polyhedron,Bipartite graph,Directed graph,Quadratic equation,Linear programming,Hirsch conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
159 | 1-2 | 0025-5610 |
Citations | PageRank | References |
1 | 0.36 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Steffen Borgwardt | 1 | 13 | 2.45 |
| Elisabeth Finhold | 2 | 10 | 1.70 |
| Raymond Hemmecke | 3 | 6 | 0.93 |