On circuit diameter bounds via circuit imbalances

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Integer programming (90C10) Linear programming (90C05) Directed graphs (digraphs), tournaments (05C20)

Cites Work

Unnamed Item
Unnamed Item
A counterexample to the Hirsch conjecture
On the shadow simplex method for curved polyhedra
A strongly polynomial minimum cost circulation algorithm
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
The hierarchy of circuit diameters and transportation polytopes
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
On the Circuit Diameter of Some Combinatorial Polytopes
Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization
On sub-determinants and the diameter of polyhedra
Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
Minimum cost flows, MDPs, and ℓ ₁ -regression in nearly linear time for dense instances
Circuit Imbalance Measures and Linear Programming
Circuits in extended formulations

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