On circuit diameter bounds via circuit imbalances
From MaRDI portal
Publication:6589764
DOI10.1007/S10107-024-02107-XMaRDI QIDQ6589764FDOQ6589764
Authors: Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh 
Publication date: 20 August 2024
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Recommendations
Linear programming (90C05) Directed graphs (digraphs), tournaments (05C20) Integer programming (90C10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)
Cites Work
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- Sensitivity theorems in integer linear programming
- On sub-determinants and the diameter of polyhedra
- A primal-dual interior point method whose running time depends only on the constraint matrix
- A strongly polynomial minimum cost circulation algorithm
- A polynomial cycle canceling algorithm for submodular flows
- Finding minimum-cost circulations by canceling negative cycles
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- On the circuit diameter of dual transportation polyhedra
- A counterexample to the Hirsch conjecture
- Variation of cost functions in integer programming
- Edges versus circuits: a hierarchy of diameters in polyhedra
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- A quasi-polynomial bound for the diameter\\of graphs of polyhedra
- Circuit Imbalance Measures and Linear Programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
- Improving bounds on the diameter of a polyhedron in high dimensions
- Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
- Geometric random edge
- Finding short paths on polytopes by the shadow vertex algorithm
- On the shadow simplex method for curved polyhedra
- Subspaces with well-scaled frames
- Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
- The hierarchy of circuit diameters and transportation polytopes
- The minimum mean cycle-canceling algorithm for linear programs
- On the circuit diameter of some combinatorial polytopes
- On the circuit diameter conjecture
- An implementation of steepest-descent augmentation for linear programs
- Minimum cost flows, MDPs, and ℓ 1 -regression in nearly linear time for dense instances
- Pivot rules for circuit-augmentation algorithms in linear optimization
- Circuits in extended formulations
Cited In (1)
This page was built for publication: On circuit diameter bounds via circuit imbalances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6589764)
