Approximation Algorithms (APX)
Many important computational problems are difficult or impossible to solve exactly or optimally. For example,
- many optimization problems are NP-hard,
- some problems have inputs so large that exact algorithms are infeasible, and
- some problems require decisions to be made on-line, based on incomplete information.
Instead, we use approximation algorithms to efficiently find solutions that are provably close in quality to the exact or optimal solutions.
The course covers techniques for designing and analysing approximation algorithms for various computational problems, focusing on optimization algorithms, sublinear algorithms, and on-line algorithms. It is aimed at students who like to use mathematics to design and analyze algorithms.
The topics mentioned under Learning Outcome are covered in lectures and worked on in exercises in order to develop the necessary skills and competences.
MSc Programme in Computer Science
- Greedy algorithms
- Rounding data and dynamic programming
- Rounding of linear programs and semidefinite programs
- Streaming algorithms for distinct elements, multisets, and ordered sets
- Competitive analysis for on-line algorithm
- Proving approximation guarantees for optimization, streaming, and on-line algorithms
- Using linear programming as a basis for designing approximation algorithms
- Using randomization to design approximation algorithms
- Extending approximation algorithms seen in the course to a more general setting, or to related settings.
- Apply approximation algorithms seen in the course to solve new computational problems.
- Communicate effectively about the theory of approximation algorithms, both for accessing advanced topics from the research literature and for convincingly presenting the results of own work.
Lectures and compulsory assignments.
Expected to be:
- The Design of Approximation Algorithms by Shmoys and Williamson.
- Small Summaries for Big Data by Cormode and Yi.
- Various lecture notes or papers.
The books are currently available for free online.
The students should be comfortable with formal, mathematical
reasoning, as the course uses the power of mathematics to
understand and prove good performance of algorithms. It is assumed
that the students have completed an algorithms course such as
Advanced Algorithms and Data Structures, and are comfortable using
mathematical proofs in the analysis of algorithms.
Academic qualifications equivalent to a BSc degree is recommended.
PhD’s can register for MSc-course by following the same procedure as credit-students, see link above.
- 7,5 ECTS
- Type of assessment
Oral examination, 30 minutes (including grading)
- Type of assessment details
- The oral examination is with 30 minutes preparation.
- All aids allowed
- Marking scale
- 7-point grading scale
- Censorship form
- No external censorship
Several internal examiners
Criteria for exam assessment
See Learning Outcome.
Single subject courses (day)
- Course number
- 7,5 ECTS
- Programme level
- Full Degree Master
- Block 4
- No limit
The number of seats may be reduced in the late registration period
- Study Board of Mathematics and Computer Science
- Department of Computer Science
- Faculty of Science
- Rasmus Pagh (4-7f7076774f73783d7a843d737a)
Are you BA- or KA-student?
Courseinformation of students