Approximation algorithms Basic Information I071 (2+2+0) - 6 ECTS credits Students will be introduced to fundamental and advanced principles in approximation algorithm design for combinatorial optimization problems for which no exact solution can be found efficiently. In this course, student will learn complexity analysis techniques for analysing problems and its approximability, i.e. how efficiently can one problem be approximated. Using linear and semidefinite programming theory students will develop methods for designing and analysing approximation algorithms. Several known combinatorial optimization problems and their approximation algorithms will be demonstrated. You can access the course content at the following link: PDF Teachers Basic literature V. Vazirani, Approximation Algorithms, Springer, 2011. D. P. Williamson, D.B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011. Additional literature B. Gaertner, J. Matoušek, Approximation Algorithms and Semidefinite Programming, Springer, 2012. D. Hochbaum, Approximation Algorithms for NP-hard Problems, Course Technology, 1 Ed, 1996. B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2018. C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover publications, 1998. Teaching materials The materials are available on the internal Teams channel of the course, through which all internal communication takes place. Students are required to register on the course’s Teams channel. The channel code for joining the course can be found in the schedule.