On circuit diameter bounds via circuit imbalances
From MaRDI portal
Publication:2164689
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
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)
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