Starten

8 Approximationsalgorithmen

Scheduling unabhängiger gewichteter Jobs auf parallelen Machinen

List Scheduling

Viele Kleine Jobs

Der Approximationsfaktor

Diese Schranke is bestmöglich

Mehr zu Scheduling

Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP)

TSP mit Dreiecksungleichung

2-Approximation durch minimalen Spannbaum

Beispiel

Mehr TSP

Pseudopolynomielle Algorithmen

Beispiel Rucksackproblem

Dynamische Programmierung nach Profit

Fully Polynomial Time Approximation Scheme

FPTAS für Knapsack

Das beste bekannte FPTAS

Fully Polynomial Time Approximation Scheme

Optimale Algorithmen für das Rucksackproblem

9 Fixed-Parameter-Algorithmen

Beispiel: VERTEX COVER (Knotenüberdeckung)

VERTEX COVER Grundlegendes

FIxed parameter tractable

Naive tiefenbeschränkte Suche

Kernbildung für Vertex Cover