On circuit diameter bounds via circuit imbalances

DOI10.1007/978-3-031-06901-7_11zbMath1502.52013arXiv2111.07913OpenAlexW3213177103MaRDI QIDQ2164689

Bento Natura, Zhuan Khye Koh, László A. Végh, Daniel Dadush

Publication date: 16 August 2022

Full work available at URL: https://arxiv.org/abs/2111.07913

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Integer programming (90C10) Linear programming (90C05)

Related Items (1)

A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

Cites Work

• Unnamed Item
• A counterexample to the Hirsch conjecture
• On the shadow simplex method for curved polyhedra
• Subspaces with well-scaled frames
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• A primal-dual interior point method whose running time depends only on the constraint matrix
• Variation of cost functions in integer programming
• Edges versus circuits: a hierarchy of diameters in polyhedra
• A polynomial cycle canceling algorithm for submodular flows
• Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
• On the circuit diameter conjecture
• The minimum mean cycle-canceling algorithm for linear programs
• An implementation of steepest-descent augmentation for linear programs
• Improving bounds on the diameter of a polyhedron in high dimensions
• Geometric random edge
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• On the Circuit Diameter of Dual Transportation Polyhedra
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• Finding minimum-cost circulations by canceling negative cycles
• Sensitivity theorems in integer linear programming
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Stable Numerical Algorithms for Equilibrium Systems
• On the Circuit Diameter of Some Combinatorial Polytopes
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
• A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
• On sub-determinants and the diameter of polyhedra
• Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks

This page was built for publication: On circuit diameter bounds via circuit imbalances