Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes

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

Mathematics Subject Classification ID

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