Each module contains 3 ECTS. You choose a total of 10 modules/30 ECTS in the following module categories:
- 12-15 ECTS in technical scientific modules (TSM)
TSM modules teach profile-specific specialist skills and supplement the decentralised specialisation modules. - 9-12 ECTS in fundamental theoretical principles modules (FTP)
FTP modules deal with theoretical fundamentals such as higher mathematics, physics, information theory, chemistry, etc. They will teach more detailed, abstract scientific knowledge and help you to bridge the gap between abstraction and application that is so important for innovation. - 6-9 ECTS in context modules (CM)
CM modules will impart additional skills in areas such as technology management, business administration, communication, project management, patent law, contract law, etc.
In the module description (download pdf) you find the entire language information per module divided into the following categories:
- instruction
- documentation
- examination
An algorithm is typically called efficient if its worst-case running time is polynomial in the size of the input. This course will focus on a huge and practically relevant family of problems, namely NP-hard ones, for which (most likely) no efficient algorithm exists. This family includes fundamental problems in computational biology, network design, systems, computer vision, data mining, online markets, etc.
The first goal of this course it to learn how to identify NP-hard problems.
For a given NP-hard optimization problem it might still be possible to compute efficiently a feasible solution whose cost is (in the worst-case) within a small multiplicative factor (approximation factor) from the optimum: this is the aim of approximation algorithms. The second goal of this course is to learn how to design accurate approximation algorithms, and how to (theoretically) bound their approximation factor.
Prerequisites
Basics of theoretical analysis of algorithms.
Learning Objectives
The main goal of this course is to learn how to identify NP-hard problems, and how to design and (theoretically) analyze approximation algorithms for fundamental NP-hard optimization problems.
Contents of Module
A. Complexity Classes: polynomial Reductions; NP-completeness and NP-hardness.
B. NP-hard problems: SAT and Max-SAT; Vertex/Set Cover; Steiner Tree and generalizations; TSP; Max Cut; Knapsack and Bin Packing; k-Center and clustering; Scheduling; Facility Location; Item Pricing; etc.
C. Approximation Algorithms:
- Basic notions: approximation factor; hardness of approximation.
- Basic techniques: greedy; local search; randomization; dynamic programming.
LP-based techniques: randomized rounding; primal-dual; iterative rounding.
Teaching and Learning Methods
Interactive lectures both for theory and exercises.
Literature
- V. V. Vazirani. Approximation Algorithms. Springer.
- D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press.
Download full module description
Back