Approximation Algorithms

Worum geht's

Du lernst, wie man effiziente Näherungsalgorithmen für kombinatorische Optimierungsprobleme entwirft und analysiert. Am Ende kannst du Laufzeit und Approximationsgarantien von Algorithmen beurteilen, bekannte Techniken (z. B. Greedy, LP-Rounding, Primal-Dual) anwenden und Grenzen der Approximierbarkeit nachweisen.

Was du danach kannst

• Verstehen grundlegender Techniken für Approximationen (Greedy, LP-Rounding, Primal-Dual)
• Analyse von Laufzeit und Approximation guarantee
• Entwurf neuer Approximationalgorithmen für kombinatorische Probleme
• Begründung von Inapproximierbarkeitsresultaten

Aus was das Modul besteht

• VorlesungVermittlung der Konzepte und Techniken; Inhalte werden vorab in Videos bereitgestellt und in Präsenz diskutiert
• ÜbungenBearbeitung von Übungsaufgaben und Diskussion der Ansätze mit den Übungsleitenden

Lehrmethode

• Flipped ClassroomLerninhalte werden vorab in Videos vermittelt, die Präsenzzeit dient der Diskussion und Klärung
• Problemblätter und DiskussionÜbungsaufgaben vertiefen das Verständnis und erlauben Rückfragen im Übungsformat
• Online-Votings in der VeranstaltungInteraktive Einbindung zur Aktivierung und Einordnung von Verständnisfragen
• Individuelle DiskussionGelegenheiten, einzelne Fragen persönlich oder in kleinen Gruppen zu klären