CSAIL Event Calendar: Previous Series
Cost Shares and Approximation Algorithms for Network Design Problems
Speaker: Lisa Fleischer , IBM
Relevant URL: http://theory.csail.mit.edu/~sethg/cgi/blosxom.cgi/fleischer.html
Cost shares are a well-known concept from the realm of mechanism design. Recently, cost shares have also proved to be a useful tool in analyzing approximation algorithms for various network design problems. We build on this work by introducing very simple cost shares for Steiner forest problems, derived from primal-dual approximation algorithms. The result is simpler analyses and better approximation guarantees for two interesting network design problems, one modeling economies of scale (multicommodity rent-or-buy), the second modeling uncertainties in demand (stochastic Steiner tree). In this talk, I'll review the most relevant previous work and then discuss our new results.