Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Introduction
verfasst von : Ding-Zhu Du, Ker-I Ko, Xiaodong Hu
Erschienen in: Design and Analysis of Approximation Algorithms
Verlag: Springer New York
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
When exact solutions are hard to compute, approximation algorithms can help. In this chapter, we introduce the basic notions of approximation algorithms.We study a simple optimization problem to demonstrate the tradeoff between the time complexity and performance ratio of its approximation algorithms. We also present a brief introduction to the general theory of computational complexity and show how to apply this theory to classify optimization problems according to their approximability.