CMU Campus
 Faculty in  Mathematical  Finance            
Math Finance Home Conferences Seminars People Open Positions Contact

Probability and Math Finance Seminar

David Goldberg, MIT

PTAS for maximum weight independent set problem with random weights in bounded degree graphs

Abstract: We consider a new framework for studying average-case complexity of NP-hard problems, in which the underlying graph instance is worst-case but the cost vector is drawn randomly. As an illustration, we construct a simple randomized PTAS for finding the Maximum Weight Independent Set in graphs of maximum-degree 3 when the weights are drawn i.i.d. from the exponential distribution, even though the cardinality-version of the same problem is NP-hard to approximate to within a factor of 1.0071. We extend the results to graphs of higher degree, when the nodes are weighted by mixtures of exponential distributions. We also prove that if one fixes the distribution but increases the maximum degree of the underlying instance, one hits a complexity-theoretic barrier similar to that found in standard worst-case analyses. We also relate this framework to the general question of when `randomness' induces a localization in problem structure, and several related questions from statistical physics and the analysis of algorithms. This is joint work with Theophane Weber and David Gamarnik.

MONDAY, November 23, 2009
Time: 5:00 P.M.
Location: WeH 6423