Seminar zu Approximationsalgorithmen (211118-SoSe23)

Viele Optimierungsprobleme, die in der Praxis auftreten, sind NP-schwer, so dass für diese keine polynomiellen Algorithmen bekannt sind. Ein Ansatz, um diese dennoch zu lösen, sind approximative Algorithmen. Dies sind Algorithmen die nicht zwingend die optimale Lösung finden, aber eine Lösung die nicht viel schlechter als die optimale Lösung ist. In diesem Seminar betrachten wir Approximationsalgorithmen für eine Reihe klassischer Optimierungsprobleme, wie zB dem Travelling Salesman Problem. Das Seminar richtet sich an Studierende im Bachelor und Master und orientiert sich an dem Buch "Approximation Algorithms" von Vijay V. Vazirani (Springer, 2001).