**Monday, July 4, 2011**

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

room 005

** Lecture - 14:15**

*Abstract:*

The simplex algorithm is among the most widely used algorithms for solving
linear programs in practice. Most deterministic pivoting rules are known,
however, to require an exponential number of steps to solve some linear
programs. No non-polynomial lower bounds were known, prior to this work,
for randomized pivoting rules. We provide the first subexponential (i.e., of
the form $2^{\Omega(n^\alpha)}$, for some $\alpha>0$) lower bounds for the
two most natural, and most studied, randomized pivoting rules suggested to date.

The first randomized pivoting rule we consider is Random-Edge, which
among all improving pivoting steps (or edges) from the current basic feasible
solution (or vertex) chooses one uniformly at random. The second randomized pivoting
rule we consider is Random-Facet, a more complicated randomized pivoting
rule suggested by Kalai (1992) and Matou{\v{s}}ek, Sharir and Welzl (1996).

Our lower bound for the Random-Facet pivoting rule essentially matches the
subexponential upper bounds of Kalai and Matou{\v{s}}ek et al. Lower
bounds for Random-Edge and Random-Facet were known before only in abstract
settings, and not for concrete linear programs.

Our lower bounds are obtained by utilizing connections between pivoting
steps performed by simplex-based algorithms and improving switches performed by
policy iteration algorithms for 1-player and 2-player games. We start by
building 2-player parity games (PGs) on which suitable randomized policy
iteration algorithms perform a subexponential number of iterations. We then
transform these 2-player games into 1-player Markov Decision Processes
(MDPs) which correspond almost immediately to concrete linear programs.

Joint work with Thomas Dueholm Hansen and Oliver Friedmann

**Colloquium - 16:00**

*Abstract:*

We are given some geometric data in the form of a set P of n points in R^d.
Then the aim of combinatorial data approximation is to give a succinct
summary of the shape of P (e.g., spread and distribution of the points
in P). This becomes especially important as the data becomes
unmanageably large (e.g., coming from a live-stream), and so only a
small 'sketch' can be stored. In this talk I will present various
algorithms and techniques for approximating a set of points with a
smaller set.

I will first present and explain the notion of a centerpoint, which is
the generalization of the concept of a median to higher dimensions.
Then I will present various related notions, including Simplicial-depth.
and Ray-shooting depth. Some recent results, as well as several open
problems will be presented.

Letzte Aktualisierung:
21.06.2011