Polynomial Time Approximation Schemes for Some Dense Instances of NP‐Hard Optimization Problems

Polynomial Time Approximation Schemes for Some Dense Instances of NP‐Hard Optimization Problems

0.00 Avg rating0 Votes
Article ID: iaor20121043
Volume: 30
Issue: 3
Start Page Number: 386
End Page Number: 397
Publication Date: Jan 2001
Journal: Algorithmica
Authors:
Keywords: literature survey, NP-hard, polynomial programs
Abstract:

We survey recent results on the existence of polynomial time approximation schemes for some dense instances of NP‐hard combinatorial optimization problems. We indicate some inherent limits for the existence of such schemes for some other dense instances of optimization problems. We also go beyond the dense optimization problems and show how other approximation problems can be solved by using dense techniques.

Reviews

Required fields are marked *. Your email address will not be published.