Combinatorial Optimization

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.

• Jumping doesn't help in abstract cubes, (with I. Schurr) Eleventh Conference on Integer Programming and Combinatorial Optimization (IPCO) 2005, 225-235.
  We give exponential lower bounds on the running time of two deterministic processes BOTTOMANTIPODAL and BOTTOMTOP in abstract cubes. An abstract cube is defined by a function on the vertices of the usual cube polytope, such that there is exactly one local maximum on any face of the cube. Obviously any generic linear objective function on a cube-like polytope has this property.
  BOTTOMANTIPODAL was suggested by Kaibel, I suppose partly out of frustration about the numerous (theoretically) unsuccessful deterministic simplex pivot rules. It is a very non-simplex-like algorithm, which takes not only one of the improving edges into account, but, in some sense all of them. Of course in order to abandon the idea of progress along an edge, one needs to know something about the structure of the polytope. For example, when our polytope is combinatorially equivalent to the n-dimensional cube, then it makes sense to speak about an ``antipodal vertex''. Each vertex is at the bottom of the face generated by its improving edges, as it is the minima of this face. Motivated by the picture of the orthogonal cube, the algorithm BOTTOMANTIPODAL jumps from the bottom vertex of the face generated by its improving edges to the antipodal vertex within this face.
  The process called BOTTOMTOP, also suggested by Kaibel, in some sense represents the most greedy approach one can imagine without remembering the history. Being at a vertex v and knowing the incident improving edges, one knows that every vertex in the face generated by these improving edges is better than the current vertex. Suppose we have access to an oracle which tells us the best vertex, i.e. the maxima, in this subcube, and thus we are able to jump there in one step. It is then plausible to believe this to be a good idea. A step of the process BOTTOMTOP is defined by jumping from the current vertex v to the maxima v' in the subcube generated by the improving edges incident to v. BOTTOMTOP is of course not an algorithm, since we need to have access to an oracle which tells us the sink of a subcube once we provide the source.
  In the paper it turns out that none of these two processes are a good idea; at least in the setting of abstract cubes. We do not know their behaviour in realizable cubes or even in cubes satisfying the Holt-Klee condition in every three dimensional subcube.


• RANDOM EDGE can be exponential on abstract cubes, (with J. Matoušek) Advances in Mathematics, 204(2006) 262-277.
  An extended abstract appeared in Proc. 45nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS), (2004), 92-100.
  We study the behavior of RANDOMEDGE (the random simplex algorithm which proceeds on an improving edge selected uniformly at random) on abstract cubes. An abstract cube is defined by a function on the vertices of the usual cube polytope, such that there is exactly one local minimum on any face of the cube. Obviously any linear objective function on a cube-like polytope has this property. It was conjectured that RANDOMEDGE is quadratic on any abstract cube. In the paper an abstract cube is constructed on which RANDOMEDGE performs a mildly exponential number of steps in expectation.
  We do not know the behaviour of RANDOMEDGE in realizable cubes or even in cubes satisfying the Holt-Klee condition in every three dimensional subcube.


• Finding the sink takes some time, (with I. Schurr), Discrete and Computational Geometry, 31 (2004) 627-642.
  An extended abstract appeared in Proc. 10th European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 2461 (2002) 833-844.
  The first nonlinear worst-case lower bound is given for the running time of any deterministic algorithm which finds the sink of a unique sink orientation in the vertex oracle model. This lower bound is n²/log n, and works even for acyclic unique sink orientations. The proof is based on two simple, yet quite effective lemma which describe some ways to construct new unique sink orientations from old ones. These lemmas has already seen some other applications (see for example the paper above).


• Unique sink orientations of cubes, (with E. Welzl), Proc. 42nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS), (2001) 547-555.
  The main goal of the paper is to introduce the model of unique sink orientations of cubes as a general framework for several optimization problems in geometry, like linear programming or smallest enclosing ball. An orientation of the edges of the hypercube is called unique sink orientation if all subcubes have exactly one sink (a vertex with only incoming edges). The orientation is given to us implicitly: when we query a vertex, an oracle tells us the orientation of all the incident edges. One such operation is called vertex evaluation. We would like to evaluate the sink in as few steps as possible. Obviously when the orientation is acyclic then the model includes Linear Programming on polytopes combinatorially equivalent to the cube. Gärtner and Schurr showed that the model of unique sink orientations of cubes (when cycles are also allowed) contains Linear Programming on an arbitrary polyhedron. In view of this reduction the main advantage of our model is that one can jump around and is not forced to proceed in a simplex-like fashion, which is otherwise hard to avoid on some arbitrary polyhedron.
  Basic properties of unique sink orientations of cubes are established, several algorithms are given. As the algorithmic bounds are still almost as far apart as they could be, a lot of very interesting open questions remain.