Computer Science/Discrete Mathematics Seminar I

Given a polytope P with a real-valued objective function f on its vertices, we consider the problem of finding a minima of f. Arguably the simplest randomized approach is the simplex algorithm RANDOMEDGE. Sitting at a vertex of P, RANDOMEDGE chooses an edge uniformly at random among all incident edges decreasing the objective function value, and proceeds on it to the neighboring vertex. In the most important special case, i.e. when f is given by a linear function, the performance of RANDOMEDGE is not known. The most widely studied combinatorial generalization of linear functions is the concept of "abstract objective function". Abstract objective functions have a unique minima on every face, which is certainly true for generic linear functions. It was conjectured that RANDOMEDGE finds the minima of abstract objective functions in polynomial or even quadratic expected time. In the talk we exhibit an abstract objective function on the n-dimensional hypercube, such that RANDOMEDGE takes a mildly exponential expected time to find its minima. Joint work with J. Matousek.