Friday, October 19, 2007 



GroupStrategy Proof Mechanisms for Network Design Games 

About 15 years ago, Goemans and Williamson formally introduced the
primaldual framework for approximation algorithms and applied it to a
class of network design optimization problems. Since then literally
hundreds of results appeared that extended, modified and applied the
technique to a wide range of optimization problems. 