On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
From MaRDI portal
Publication:3457191
DOI10.1137/151002915zbMath1330.90053arXiv1408.3518OpenAlexW1528072933MaRDI QIDQ3457191
Jesús A. De Loera, Raymond Hemmecke, Jon Lee
Publication date: 11 December 2015
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1408.3518
Related Items
Quadratic diameter bounds for dual network flow polyhedra, On circuit diameter bounds via circuit imbalances, Solving MIPs via scaling-based augmentation, A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs, Heat-bath random walks with Markov bases, An implementation of steepest-descent augmentation for linear programs, Circuit walks in integral polyhedra, Inapproximability of shortest paths on perfect matching polytopes, A scaling algorithm for optimizing arbitrary functions over vertices of polytopes, Constructing Clustering Transformations, On the Circuit Diameter of Some Combinatorial Polytopes, On the circuit diameter conjecture, A note on the approximability of deepest-descent circuit steps, A polyhedral model for enumeration and optimization over the set of circuits, A Generalized Simplex Method for Integer Problems Given by Verification Oracles, Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization, A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix, Lower bounds on the graver complexity of \(M\)-fold matrices
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A polynomial oracle-time algorithm for convex integer minimization
- The Graver complexity of integer programming
- A finiteness theorem for Markov bases of hierarchical models
- \(N\)-fold integer programming
- Nonlinear discrete optimization. An algorithmic theory
- An application of simultaneous diophantine approximation in combinatorial optimization
- Subspaces with well-scaled frames
- Decomposition of regular matroids
- On the computational behavior of a polynomial-time network flow algorithm
- The generalized simplex method
- Test sets for integer programs
- A polynomial time primal network simplex algorithm for minimum cost flows
- Higher Lawrence configurations.
- On the positive sums property and the computation of Graver test sets
- Edges versus circuits: a hierarchy of diameters in polyhedra
- \(n\)-fold integer programming in cubic time
- A bound for the number of different basic solutions generated by the simplex method
- The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
- On Greedy and Submodular Matrices
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- On the Circuit Diameter of Dual Transportation Polyhedra
- Combinatorics and Geometry of Transportation Polytopes: An Update
- Packing and covering with integral feasible flows in integral supply-demand networks
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- On the foundations of linear and integer linear programming I
- A counterexample to an integer analogue of Carathéodory's theorem
- The Complexity of Generic Primal Algorithms for Solving General Integer Programs
- On sub-determinants and the diameter of polyhedra
