Volker Turau, Christoph Weyer
Algorithmische
Graphentheorie

Algorithmische Graphentheorie


Kapitel 11: Approximative Algorithmen


In diesem Kapitel werden Probleme behandelt, für die es höchstwahrscheinlich nur Algorithmen mit exponentieller Laufzeit gibt. Zunächst wird eine relativ informelle Einführung in die Komplexitätsklassen P, NP und NPC gegeben. Danach werden approximative Algorithmen eingeführt, und es werden Maßzahlen definiert, mit denen die Qualität dieser Algorithmen charakterisiert werden kann. Diese Maßzahlen sind zum einen wichtig, um verschiedene approximative Algorithmen zu vergleichen und zum anderen, um eine Abschätzung der Abweichung der erzeugten Lösung von der optimalen Lösung zu haben. Unter der Voraussetzung P≠NP wird gezeigt werden, dass die meisten NP-vollständigen Probleme keine approximativen Algorithmen mit beschränktem absoluten Fehler besitzen. Ferner wird gezeigt, dass sich die Probleme aus NPC bezüglich der Approximierbarkeit mit beschränktem relativen Fehler sehr unterschiedlich verhalten. Danach werden approximative Algorithmen für fünf klassische Probleme der algorithmischen Graphentheorie vorgestellt. Am Ende dieses Kapitels wird das Traveling-Salesman Problem ausführlich behandelt.

Kapitelübersicht

  1. Einleitung
  2. Einführung
  3. Bäume
  4. Suchverfahren in Graphen
  5. Entwurfsmethoden für die algorithmische Graphentheorie
  6. Färbung von Graphen
  7. Perfekte Graphen
  8. Flüsse in Netzwerken
  9. Anwendungen von Netzwerkalgorithmen
  10. Kürzeste Wege
  11. Approximative Algorithmen
    1. Die Komplexitätsklassen P, NP und NPC
    2. Einführung in approximative Algorithmen
    3. Absolute Qualitätsgarantien
    4. Relative Qualitätsgarantien
    5. Approximative Algorithmen
    6. Das Problem des Handlungsreisenden
    7. Literatur
    8. Aufgaben