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

DOI10.1007/s11750-013-0291-yzbMath1311.52010OpenAlexW1978428710MaRDI QIDQ5965568

Jesús A. De Loera

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

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial aspects of simplicial complexes (05E45)

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