Dan Bienstock, Lecture 3

Oblivious Rounding and Derivatives

In this talk we present a novel idea due to Neal Young that exploits the strength of the probabilistic method to yield provably good deterministic approximation algorithms for classes of combinatorial problems and linear programs.

The central paradigm used by this approach is to imagine that an adversary has computed an optimal solution to an optimization problem. We can query the adversary for information on this optimal solution, but what we will receive will be repeated or obfuscated information.

By repeatedly querying the adversary we can, in some cases, obtain a randomized algorithm that has positive probability of success after a polynomial number of queries. By further exploiting the power of randomness (and repeated sampling) we are finally able to deconstruct the process used by the adversary and obtain our desired deterministic approximation algorithm.

This approach, extended by Garg and Koenemann, and Fleischer, has produced the fastest approximation algorithms for e.g. multicommodity flow problems.

Back to the IPCO VIII Program.