PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs.

David Gamarnik, David A. Goldberg, Theophane Weber

Browse the full SODA paper archive.