Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

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