Combinatorial Optimization

Tibor Szabó

Institute of Mathematics
Freie Universität Berlin

Combinatorial Optimization is a very wide field and I worked only on a small segment of it: unique sink orientations of cubes, which involves certain combinatorial problems originating from Linear Programming. We interpret LP as a geometric problem: given a polytope P with m facets in the n dimensional Euclidean space and a linear objective function c, we would like to find the maximum of c over P. The major question here is to decide whether there exists an algorithm which is polynomial in n and m, provided arithmetic operations incur unit costs. (Note that there are algorithms polynomial in the bit size of the input.) The first and in some cases still most successful idea to attack this problem is the simplex algorithm, which, after starting at some vertex of the polytope goes from vertex to a neighboring vertex, always following an improving edge. Of course at each vertex there might be several options to improve; the way of selecting the next vertex is the pivot rule. Although there are numerous pivot rules which are quite efficient in practice, there is no theoretical guarantee about any of them. Even more discouragingly all but one deterministic pivot rules suggested so far have exponential worst case examples. Randomized pivot rules are more promising; there is at least one (due to Kalai, and, independently to Matousek, Sharir and Welzl) which has subexponential expected running time.

Valid HTML 4.0! Last modified: Sun Jun 30 22:54:26 CEST 2013