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,
225235.
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 cubelike 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 nonsimplexlike 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
ndimensional 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 HoltKlee condition in every three dimensional
subcube.

RANDOM EDGE can be exponential on abstract cubes,
(with J. Matoušek)
Advances in Mathematics, 204(2006) 262277.
An extended abstract appeared in
Proc. 45nd Ann. IEEE Symp. on Foundations of Computer Science
(FOCS),
(2004), 92100.
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 cubelike 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 HoltKlee condition in every three dimensional
subcube.

Finding the sink takes some time, (with I. Schurr),
Discrete and Computational Geometry,
31 (2004) 627642.
An extended abstract appeared in
Proc. 10th European Symposium on Algorithms (ESA),
Lecture Notes in Computer Science 2461 (2002) 833844.
The first nonlinear worstcase 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^{2}/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) 547555.
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 simplexlike
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.
Last modified: Sun Jun 30 22:54:26 CEST 2013