abstract
Recent years have brought some progress in the knowledge of
the complexity of linear programming in the {\em unit cost model},
and the best result known at this point is
a {\em randomized `combinatorial'} algorithm which solves a linear program
over $d$ variables and $n$ constraints
with expected $$O(d^2 n + e^{O(\sqrt{d \log d})})$$
arithmetic operations. The bound relies
on two algorithms by Clarkson, and the
subexponential algorithms due to Kalai, and to
Matou\v{s}ek, Sharir \& Welzl.
We review some of the recent algorithms with their analyses. We
also present abstract frameworks like {\em LP-type problems} and
{\em abstract optimization problems} (due to G\"artner) which allow
the application of these algorithms to a number of
non-linear optimization problems (like polytope distance
and smallest enclosing ball of points).
Back to the publications page
