Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!OKANE.CS.UMASS.EDU!patrick
From: patrick@OKANE.CS.UMASS.EDU (Patrick Healy)
Newsgroups: comp.theory
Subject: Max Indep Set
Message-ID: <9001101346.AA00598@okane.cs.umass.edu>
Date: 10 Jan 90 15:21:52 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Patrick Healy <patrick%okane.cs.umass.edu@VM1.NoDak.EDU>
Lines: 14

>        Does anyone have pointers to a practical approximation
>algorithm for the maximum independent set problem?

>                                Thanks,  Joan Lucas


I would be interested in approximation algorithms (or references) to the
weighted version of ths problem i.e., Maximum Weighted Independent Set.  I've
seen references to some special cases of the related problem: Maximum Weighted
Clique, but nothing for the general case.

Any pointers would be appreciated.  Thanks,
Pat Healy,
Univ. of Mass, Amherst.