510009 VU VGSCO: Approximation Algorithms (2022S)
Prüfungsimmanente Lehrveranstaltung
Labels
An/Abmeldung
Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").
- Anmeldung von Mo 16.05.2022 00:00 bis Do 02.06.2022 23:59
- Abmeldung bis Do 09.06.2022 23:59
Details
max. 25 Teilnehmer*innen
Sprache: Englisch
Lehrende
Termine (iCal) - nächster Termin ist mit N markiert
- Mittwoch 08.06. 09:45 - 11:15 Seminarraum 11 Oskar-Morgenstern-Platz 1 2.Stock
- Mittwoch 08.06. 13:15 - 14:45 Seminarraum 13 Oskar-Morgenstern-Platz 1 2.Stock
- Donnerstag 09.06. 09:45 - 11:15 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Donnerstag 09.06. 13:15 - 14:45 Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
- Montag 13.06. 09:45 - 11:15 Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
- Montag 13.06. 13:15 - 14:45 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Dienstag 14.06. 09:45 - 11:15 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Dienstag 14.06. 13:15 - 14:45 Seminarraum 6 Oskar-Morgenstern-Platz 1 1.Stock
- Mittwoch 15.06. 09:45 - 11:15 Seminarraum 11 Oskar-Morgenstern-Platz 1 2.Stock
- Mittwoch 15.06. 13:15 - 14:45 Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
- Freitag 17.06. 09:45 - 11:15 Seminarraum 11 Oskar-Morgenstern-Platz 1 2.Stock
- Freitag 17.06. 13:15 - 14:45 Seminarraum 12 Oskar-Morgenstern-Platz 1 2.Stock
Information
Ziele, Inhalte und Methode der Lehrveranstaltung
This course will present an introduction to the topic of approximation algorithms for problems in combinatorial optimization. Approximation algorithms are efficient algorithms that provide provably near-optimal solutions for these problems. The aim of the course is to introduce the student to a set of algorithmic approaches for designing approximation algorithms, including greedy algorithms, local search algorithms, dynamic programming, deterministic and randomized rounding of linear programs, semidefinite programming, and the primal-dual method. We'll apply these techniques to problems such as set cover, scheduling problems, maximum satisfiability, maximum cut, facility location, bounded-degree spanning trees, and the traveling salesman problem.
Art der Leistungskontrolle und erlaubte Hilfsmittel
There will be one problem homework set released per day starting with the second class.
Mindestanforderungen und Beurteilungsmaßstab
There is no formal prerequisite. In practice, I will be assuming some previous exposure
either to algorithms or combinatorial optimization, and some ability to do mathematical proofs. We'll use linear programs extensively, but I'll try to introduce what you need to go as we proceed. If you've had a
good undergraduate algorithms class that had proofs about the algorithms, you should be set. Please talk to me if
you have questions about whether you have the necessary background.
either to algorithms or combinatorial optimization, and some ability to do mathematical proofs. We'll use linear programs extensively, but I'll try to introduce what you need to go as we proceed. If you've had a
good undergraduate algorithms class that had proofs about the algorithms, you should be set. Please talk to me if
you have questions about whether you have the necessary background.
Prüfungsstoff
Literatur
The required text is ``The Design of Approximation Algorithms'', published by Cambridge University Press. An electronic version is available for free at www.designofapproxalgs.com/book.pdf.
Zuordnung im Vorlesungsverzeichnis
MAMV
Letzte Änderung: Mi 01.06.2022 05:09