kevin@argosy.UUCP (Kevin S. Van Horn) (08/22/90)
I've been reading _Computers and Intractability: A Guide to the Theory of NP-Completeness_, and was intrigued by the chapter on approaches to coping with NP-complete problems. It focuses on optimization problems, and mentions approaches such as finding a polynomial-time algorithm whose result is only guaranteed to be within some fraction of optimal, or looking for algorithms with good "average" time (even if the worst case takes exponential time), etc. The book was published in 1979, and I'm sure there must have been many new results in this area (ways of coping with NP-completeness) in the last 11 years. Can anyone suggest some more recent references? ------------------------------------------------------------------------------ Kevin S. Van Horn | The means determine the ends. kevin@argosy.maspar.com |