Quadratic diameter bounds for dual network flow polyhedra

• 成果类型: Article
• 署名作者: Borgwardt, Steffen; Finhold, Elisabeth; Hemmecke, Raymond
• 署名单位: Technical University of Munich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0956-4
• 发表日期: 2016
• 页码: 237-251
• 关键词: hirsch conjecture; transportation 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 and prove quadratic upper bounds for both of them: the minimum of and for the combinatorial diameter, and 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.