Technion Computer Science Colloquium 05/04/2011 Time+Place : Tuesday 05/04/2011 14:30 room 337-8 Taub Bld. Speaker : Uri Zwick Affiliation: Dept. of Computer Science, Tel-Aviv University Host : Johann Makowsky Title : 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 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 ---------------------------------------------------------- Visit our home page- <http://www.cs.technion.ac.il/~colloq> Wed Mar 23 11:25:21 IST 2011 --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Hadas Heier <heier@cs.technion.ac.il>