MA-INF 1206 - Seminar Randomized and Approximation Algorithms

Lecture Hours

What When Where Begin Lecturer
Seminar Wednesday, 10 - 12 2.050 19. October 2022 Heiko Röglin
Kelin Luo


In this seminar, we cover topics in the area of Randomized and Approximation Algorithms. Many optimization problems arising in theory and practice have been proved that optimal solutions cannot be computed efficiently unless P=NP. One approach to handle these problems is to design approximation algorithms, i.e., efficiently find a near-optimal solution. Randomized algorithms are another widely used approach to deal with problems for which efficient deterministic algorithms are not known.

The first meeting takes place on October 19 (Wednesday). In this meeting the topics will be assigned.

If you are interested in participating in the seminar, please send an e-mail to Kelin Luo and come to the first meeting.

If you would like to participate in the seminar but cannot attend the first meeting, please send us an email.

Example Topics

  1. Chuzhoy, Julia, Rafail Ostrovsky, and Yuval Rabani. Approximation algorithms for the job interval selection problem and related scheduling problems. Mathematics of Operations Research 31, no. 4: 730-738, 2006. (Link). [Slides by Daniel Bauer]
  2. Khani, M. Reza, and Mohammad R. Salavatipour. Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica 69, no. 2: 443-460, 2014.(Link). [Slides by Aaron Weinmann]
  3. Khani, M. Reza, Kanungo, Tapas, et al. A local search approximation algorithm for k-means clustering. Proceedings of the eighteenth annual symposium on Computational geometry. 2002. (Link).
  4. Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24:296–317, 1995. (Link).
  5. Jain, Kamal, and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM (JACM) 48, no. 2: 274-296, 2001. (Link).
  6. Bamas, Étienne, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems 33: 20083-20094, 2020. (Link). [Slides by Ulrich Stehr]
  7. Schulz, Andreas S., and Martin Skutella. Scheduling unrelated machines by randomized rounding. SIAM Journal on Discrete Mathematics 15, no. 4: 450-469, 2002. (Link).
  8. Chudak, Fabián A., and David B. Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. SIAM Journal on Computing 33.1: 1-25, 2003. (Link).
  9. Singh, Mohit, and Lap Chi Lau. Approximating minimum bounded degree spanning trees to within one of optimal. Journal of the ACM (JACM) 62.1: 1-19, 2015. (Link).
  10. McGregor, Andrew. Finding graph matchings in data streams. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer, Berlin, Heidelberg. 170-181, 2005 (Link).
  11. Michael Etscheid and Heiko Röglin. Smoothed Analysis of Local Search for the Maximum-Cut Problem. ACM Transactions on Algorithms, 13(2), 2017. (Link).
  12. Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin, and Clemens Rösner. Smoothed Analysis of the Successive Shortest Path Algorithm. SIAM Journal on Computing, 44(6):1798-1819, 2015. (Link).
  13. Tobias Brunsch, Michael Etscheid, and Heiko Röglin. Bounds for the Convergence Time of Local Search in Scheduling Problems. In Proc. of the 12th WINE (Montreal, Canada), pp. 339-353, 2016 (Link). [Slides by Ulrich Schermuly]

Page Tools