Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
From MaRDI portal
Publication:5965568
DOI10.1007/s11750-013-0291-yzbMath1311.52010MaRDI QIDQ5965568
Publication date: 28 November 2013
Published in: Top (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11750-013-0291-y
52B05: Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
90C60: Abstract computational complexity for mathematical programming problems
90C05: Linear programming
05E45: Combinatorial aspects of simplicial complexes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A counterexample to the Hirsch conjecture
- The central curve in linear programming
- Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
- A strongly polynomial algorithm for linear systems having a binary solution
- A linear bound on the diameter of the transportation polytope
- A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
- Polytopes and arrangements: diameter and curvature
- Graphs of transportation polytopes
- On relaxation methods for systems of linear inequalities
- On the complexity of following the central path of linear programs by linear extrapolation. II
- Projection algorithms for linear programming
- Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
- 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
- Criss-cross methods: A fresh view on pivot algorithms
- Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
- A subexponential bound for linear programming
- Klee-Minty's LP and upper bounds for Dantzig's simplex method
- Random edge can be exponential on abstract cubes
- On the curvature of the central path of linear programming theory
- The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
- A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
- Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes
- Smoothed analysis of algorithms
- Exponential Lower Bounds for Policy Iteration
- On the non-polynomiality of the relaxation method for systems of linear inequalities
- Lower bounds for a subexponential optimization algorithm
- The Simplex Algorithm in Dimension Three
- The Klee–Minty random edge chain moves with linear speed
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
- Two New Bounds for the Random‐Edge Simplex‐Algorithm
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Linear Inequalities
- On sub-determinants and the diameter of polyhedra
- Solving convex programs by random walks
- A simple polynomial-time rescaling algorithm for solving linear programs