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 tothis 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

SHORT BIO:

Uri Zwick received his B.Sc. degree in Computer Science from the Technion,
Israel Institute of Technology, and his M.Sc. and Ph.D. degrees in Computer
Science from Tel Aviv University. He is currently a Professor of Computer
Science in Tel Aviv University.
His main research interests are: algorithms and complexity, combinatorial
optimization, mathematical games, and recreational mathematics.


Refreshments served from 14:15 on,
 	Lecture starts at 14:30