Quadratic diameter bounds for dual network flow polyhedra

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

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2016-09, Vol.159 (1-2), p.237-251
Main Authors: Borgwardt, Steffen, Finhold, Elisabeth, Hemmecke, Raymond
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Calculus of Variations and Optimal Control
Optimization
Circuits
Combinatorial analysis
Combinatorics
Full Length Paper
Graphs
Integer programming
Linear programming
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Networks
Numerical Analysis
Polyhedra
Polyhedrons
Studies
Texts
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ) and prove quadratic upper bounds for both of them: the minimum of ( | V | - 1 ) · | E | and 1 6 | V | 3 for the combinatorial diameter, and | 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.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-015-0956-4