Large 00016

Adapting Approximation Algorithms

R. Ravi

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 1315 times.