raja@bombay.cps.msu.EDU (Narayan S. Raja) (06/01/90)
I am looking for references to probabilistic
or "randomized" algorithms which perform reasonably
well with combinatorial and other difficult problems.
By "reasonably well", I mean they could:
1. find optimal solutions in "most" cases
2. find near-optimal solutions in all cases
3. find near-optimal solutions in "most" cases
So far I have 3 references, all from the book
"Algorithms and Complexity", ed. J.F. Traub,
Academic Press, 1976. They are:
1. The Probabilistic Analysis of some Combinatorial
Search Problems -- Richard M. Karp
2. Probabilistic Algorithms -- Michael O. Rabin
3. Approximation Algorithms for Combinatorial Problems:
an annotated bibliography -- Garey and Johnson
There must have been a lot of work since 1976 :-)
so I would really appreciate any help (this is not
my area). I can summarize if it seems worthwhile.
Please EMAIL: raja@cpsvax.cps.msu.edu
raja%cpsvax.cps.msu.edu@uunet.uu.net
uunet.uu.net\!cpsvax.cps.msu.edu\!raja
Thanks in advance,
Narayan Sriranga Raja.