510009 VU VGSCO: Approximation Algorithms (2022S)
Continuous assessment of course work
Labels
Registration/Deregistration
Note: The time of your registration within the registration period has no effect on the allocation of places (no first come, first served).
- Registration is open from Mo 16.05.2022 00:00 to Th 02.06.2022 23:59
- Deregistration possible until Th 09.06.2022 23:59
Details
max. 25 participants
Language: English
Lecturers
Classes (iCal) - next class is marked with N
- Wednesday 08.06. 09:45 - 11:15 Seminarraum 11 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 08.06. 13:15 - 14:45 Seminarraum 13 Oskar-Morgenstern-Platz 1 2.Stock
- Thursday 09.06. 09:45 - 11:15 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Thursday 09.06. 13:15 - 14:45 Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
- Monday 13.06. 09:45 - 11:15 Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
- Monday 13.06. 13:15 - 14:45 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 14.06. 09:45 - 11:15 Seminarraum 10 Oskar-Morgenstern-Platz 1 2.Stock
- Tuesday 14.06. 13:15 - 14:45 Seminarraum 6 Oskar-Morgenstern-Platz 1 1.Stock
- Wednesday 15.06. 09:45 - 11:15 Seminarraum 11 Oskar-Morgenstern-Platz 1 2.Stock
- Wednesday 15.06. 13:15 - 14:45 Seminarraum 3 Oskar-Morgenstern-Platz 1 1.Stock
- Friday 17.06. 09:45 - 11:15 Seminarraum 11 Oskar-Morgenstern-Platz 1 2.Stock
- Friday 17.06. 13:15 - 14:45 Seminarraum 12 Oskar-Morgenstern-Platz 1 2.Stock
Information
Aims, contents and method of the course
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.
Assessment and permitted materials
There will be one problem homework set released per day starting with the second class.
Minimum requirements and assessment criteria
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.
Examination topics
Reading list
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.
Association in the course directory
MAMV
Last modified: We 01.06.2022 05:09