"Randomized Simplex - The Quest for Lower Bounds"

by Bernd Gaertner


In recent years, randomized variants of the simplex method have attracted some attention because of their potential to overcome the bad worst case behavior known for many deterministic variants. In this talk I want to address the question of how good randomized variants can be. As it turns out, suprisingly little is known. I want to survey some of the results and show that even in seemingly simple cases, difficult and exciting combinatorial questions can come up.

!!! Dieses Dokument stammt aus dem ETH Web-Archiv und wird nicht mehr gepflegt !!!
!!! This document is stored in the ETH Web archive and is no longer maintained !!!