Approximation Algorithms (ADM III)Module description #20091 / Version 1
- 10 CP
- Oral exam
- Graded
- Winter and summer semester
- German
| Module / Version | #20091 / #1 |
|---|---|
| Validity | Since SS 2014 |
| Available language(s) | English, German |
| Credit points | 10 |
| Person responsible for the module | Skutella, Martin |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | German |
Affiliation
| Faculty | Fakultät II |
|---|---|
| Institute | Institut für Mathematik |
| Academic chair | Not specified |
Contact
| Office | MA 5-2 |
|---|---|
| Contact person | Not specified |
| E-mail address | skutella@math.tu-berlin.de |
| Website | Not specified |
Learning outcomes
This course aims to teach the algorithmic and structural foundations of approximate solutions to combinatorial optimization problems. A major focus is on algorithms and algorithmic techniques that are based on (or whose analysis is based on) linear optimization. These include, in particular, the primal-dual scheme and LP rounds.
Subject-Specific Competence: 55% Methodological Competence: 30% System Competence: 10% Social Competence: 5%
Subject-Specific Competence: 55% Methodological Competence: 30% System Competence: 10% Social Competence: 5%
Content
Approximability and Non-approximability; Polynomial Approximation Schemes; LP Rounds: randomized, deterministic, iterated; Dual Fitting using the example of Set Cover; Primal-Dual Scheme
and Local Ratio Method Applications to network design problems Bounds from semidenite relaxations using the example of MAX CUT PCP Theorem (without proof), gap-generating reductions
Class MAX-SNP, gap-preserving reductions
and Local Ratio Method Applications to network design problems Bounds from semidenite relaxations using the example of MAX CUT PCP Theorem (without proof), gap-generating reductions
Class MAX-SNP, gap-preserving reductions
Module components
Compulsory area
The following courses are mandatory for this module:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|---|---|---|---|---|---|
| ADM III | Lecture | 3236 L 233 | Winter and summer semester | [de] | 4 | WS 2026/27 (1) ISIS |
Courses in the course catalog
Courses created from the teaching units of this module.
Winter semester 2026/27 (1)
ADM III (Lecture) 1
- ADM III (Vorlesung) Topics in Algorithmic Discrete Mathematics (ADM III) 3236 L 261
Workload and credit points
ADM III (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 4 h | 60 h |
| Preparation and follow-up review | 15 | 12 h | 180 h |
| 240 h | |||
Course-independent workload
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Exam preparation | 1 | 60 h | 60 h |
| 60 h | |||
The workload of the module adds up to 300 hours. The module therefore comprises 10 credit points.
Description of teaching and learning methods
Lectures
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
Graph and Network Algorithms (ADM I), Linear Optimization (ADM II)
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Language | German |
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Winter and summer semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
Standard.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
unavailable
Recommended literature
- Wird in der Vorlesung bekannt gegeben.
Assigned programs
This module version is used in the following programs:
| Program / program version | Semester(s) | Curriculum component |
|---|---|---|
| Business Mathematics StuPO 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| Business Mathematics Business Mathematics (M. Sc.) - StuPO 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| Computer Engineering Computer Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Computer Science (Informatik) Computer Science (Informatik) (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing | |
| Electrical Engineering Electrical Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Mathematics Mathematics (B. Sc.) - Bachelor Mathematik 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| Mathematics StuPO 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| Natural Sciences in the Information Society StuPO 2018 | SS 2025 | Wahlpflichtbereich › Mathematik |
| WS 2025/26 | Wahlpflichtbereich › Mathematik | |
| SS 2026 | Wahlpflichtbereich › Mathematik | |
| WS 2026/27 | Wahlpflichtbereich › Mathematik | |
| Natural Sciences in the Information Society Natural Sciences in the Information Society (B. Sc.) - StuPO 2025 | WS 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Mathematik |
| SS 2026 | Wahlpflichtbereich › Wahlpflichtbereich Mathematik | |
| WS 2026/27 | Wahlpflichtbereich › Wahlpflichtbereich Mathematik | |
| Technomathematics Technomathematics (M. Sc.) - StuPO 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| Technomathematics Technomathematics (B. Sc.) - StuPO 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
Miscellaneous
[Contains machine generated translations 2026-07-07 11:17, only the German version is legally binding]