# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, July 4, 2011

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

### Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

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

### Combinatorial Data-Depth of Pointsets

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