Adapting Approximation Algorithms
Recorded 12 June 2012 in Lausanne, Vaud, Switzerland
Event: SuRI - I&C - Summer Research Institute
Problems modeling several stages of uncertainty typically require solutions that must necessarily adapt to the evolving input to be (near-)optimal. We survey how linear programming methods have recently been successful in designing approximation algorithms for such multi-stage problems, even when the so-called adaptivity gap between non-adapting and adapting solutions is large.
Watched 900 times.Watch