Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!rutgers!aramis.rutgers.edu!paul.rutgers.edu!halldors
From: halldors@paul.rutgers.edu (Magnus M Halldorsson)
Newsgroups: comp.theory
Subject: Re: Max Indep Set
Message-ID: <Jan.8.12.58.58.1990.25452@paul.rutgers.edu>
Date: 8 Jan 90 17:58:59 GMT
References: <9001072141.AA22393@porthos.rutgers.edu>
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 12

In article <9001072141.AA22393@porthos.rutgers.edu> lucas@PSUVAX1.BITNET writes:

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

If you're looking for *performance guarantees* on general graphs,
you're out of luck: there are no polynomial algorithms known.

If you're thinking about good average case behaviour, the greedy
method does within a factor of 2 on random graphs.

Magnus