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.
See other events that are part of Theory Colloquium Fall 2005 |
