Anzeige
Erschienen in:
1999 | OriginalPaper | Buchkapitel
Optimization Problems, Approximation Schemes, and Their Relation with FPT
verfasst von : R. G. Downey, M. R. Fellows
Erschienen in: Parameterized Complexity
Verlag: Springer New York
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Optimization problems are at the heart of complexity theory. In practice, we usually wish to optimize some objective function (e.g., find a least-cost tour) rather than solve a related decision problem. Furthermore, even if we demonstrate that some problem has no fast solution, it is often acceptable to find an approximate solution to some desired performance ratio. In this section, we will see that parametric complexity and approximatibility are deeply related.