The Hirsch Conjecture (1957) stated that the graph of a d-dimensional polytope with n facets
cannot have (combinatorial) diameter greater than n–d. That is, any two vertices of the …

We discuss five fundamental results of discrete mathematics: the lemmas of Sperner and
Tucker from combinatorial topology and the theorems of Carathéodory, Helly, and Tverberg …

Explaining the excellent practical performance of the simplex method for linear programming
has been a major topic of research for over 50 years. One of the most successful frameworks …

The simplex algorithm is among the most widely used algorithms for solving linear programs
in practice. With essentially all deterministic pivoting rules it is known, however, to require an …

Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest
among the many existing parity game algorithms. However, its complexity is exponential …

Abstract The Hirsch Conjecture, posed in 1957, stated that the graph of ad-dimensional
polytope or polyhedron with n facets cannot have diameter greater than n− d. The conjecture …

We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting
rule converges in strongly polynomial time for deterministic Markov decision processes …

Column generation refers to linear programming (LP) algorithms designed to solve
problems in which there are a huge number of variables compared to the number of …

The Random-Facet pivoting rule of Kalai and of Matousek, Sharir and Welzl is an elegant
randomized pivoting rule for the simplex algorithm, the classical combinatorial algorithm for …

The simplex method is a well-studied and widely-used pivoting method for solving linear
programs. When Dantzig originally formulated the simplex method, he gave a natural pivot …