Paper Info
Title
PTAS for maximum weight independent set problem with random weights in bounded degree graphs
Abstract
Finding the largest independent set in a graph is a notoriously difficult N P-complete combinatorial optimization problem. Moreover, even for graphs with largest degree 3, no polynomial time approximation algorithm exists with a 1.0071-factor approximation guarantee, unless P = N P [BK98]. We consider the related problem of finding the maximum weight independent set in a bounded degree graph, when the node weights are generated i.i.d. from a common distribution. Surprisingly, we discover that the problem becomes tractable for certain distributions. Specifically, we construct a randomized PTAS (Polynomial-Time Approximation Scheme) for the case of exponentially distributed weights and arbitrary graphs with degree at most 3. We extend our result to graphs with larger constant degrees but for distributions which are mixtures of exponential distributions. At the same time, we prove that no PTAS exists for computing the expected size of the maximum weight independent set in the case of exponentially distributed weights for graphs with sufficiently large constant degree, unless P=NP. Our algorithm, cavity expansion, is new and is based on the combination of several powerful ideas, including recent deterministic approximation algorithms for counting on graphs and local weak convergence/correlation decay methods.
Year
DOI
Venue
2010
10.5555/1873601.1873624
Symposium on Discrete Algorithms
Keywords
DocType
Volume
n p,larger constant degree,bounded degree graph,independent set problem,largest independent set,optimization problem,approximation guarantee,largest degree,large constant degree,independent set,random weight,maximum weight,computational geometry,lower bound,motion planning,competitive analysis
Conference
135
ISBN
Citations 
PageRank 
978-0-89871-698-6
7
0.49
References 
Authors
10
3
Name
Order
Citations
PageRank
DAVID GAMARNIK164161.04
David A. Goldberg2212.32
Theophane Weber315916.79