Linear programming, the simplex algorithm and simple polytopes

DOI10.1007/BF02614318zbMath0887.90116OpenAlexW1981423455MaRDI QIDQ1365056

Gil Kalai

Publication date: 28 August 1997

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02614318

zbMATH Keywords

simplex algorithmsimple polytopessubexponential randomized pivot rules

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05)

Related Items (17)

The Theory of Universal Graphs for Infinite Duration Games ⋮ The Random‐Facet simplex algorithm on combinatorial cubes ⋮ The skyline algorithm for POMDP value function pruning ⋮ An exponential lower bound for Zadeh's pivot rule ⋮ Lattices from graph associahedra and subalgebras of the Malvenuto-Reutenauer algebra ⋮ Unique sink orientations of grids ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ Cyclic games and linear programming ⋮ A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games ⋮ Unnamed Item ⋮ A refinement of Todd's bound for the diameter of a polyhedron ⋮ One line and n points ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games ⋮ Book Review: The basic George B. Dantzig ⋮ An asymptotically improved upper bound on the diameter of polyhedra ⋮ A tight analysis of the submodular-supermodular procedure ⋮ Combinatorial structure and randomized subexponential algorithms for infinite games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The simplex method. A probabilistic analysis
• Puzzles and polytope isomorphisms
• A simple way to tell a simple polytope from its graph
• The number of faces of a simplicial convex polytope
• A proof of the sufficiency of McMullen's conditions for f-vectors of simplicial convex polytopes
• Small-dimensional linear programming and convex hulls made easy
• Upper bounds for the diameter and height of graphs of convex polyhedra
• Many polytopes meeting the conjectured Hirsch bound
• On simple polytopes
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Linear Programming in Linear Time When the Dimension Is Fixed
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Lower bounds for a subexponential optimization algorithm
• Lectures on Polytopes
• Las Vegas algorithms for linear and integer programming when the dimension is small
• A Subexponential Algorithm for Abstract Optimization Problems
• Paths on Polytopes
• The maximum numbers of faces of a convex polytope

This page was built for publication: Linear programming, the simplex algorithm and simple polytopes