CS-E400204 - Special Course in Computer Science D: Approximation Algorithms, Lectures, 20.4.2022-25.5.2022

Topic outline

• Approximation Algorithms
  The course will be conducted physically on campus. The lectures and other events will not be recorded and could not be participated in online.
  

  Description

  
  

  At its core, this course is about (discrete) optimization. Most central problems in the area of discrete and combinatorial optimization happen to be \( NP \)-hard. Therefore, under the popular complexity conjecture that \( NP \neq P \), we cannot hope to solve them efficiently. In many cases in the real world, we are also satisfied with a nearly good solution to our optimization problem. The discipline of approximation algorithms deals with the task of designing efficient algorithms for such problems that have a mathematically provable quality guarantee.

  In this course, we study the design and analysis techniques for Approximation Algorithms. These are efficient algorithms that can find provably good approximations of the optimum solution. We will cover some of the classical techniques of the field and we will talk about some of the more recent breakthroughs as well.
  

  Learning Objectives: Being able to use the fundamental techniques of approximation algorithm design such as

  • greedy 
  • local search
  • LP-based methods
  • ...

  for solving optimization problems. Furthermore, the students are expected to be familiar (to some extent) with various difficulty classes of optimization problems. 
  

  Lecturer: Kamyar Khodamoradi (kamyar.khodamoradi@aalto.fi)

  Teaching Assistant: Michał Osadnik (michal.osadnik@aalto.fi)

  Lectures: Mondays and Wednesdays, 16:15 - 18:00 

  
  

  Grading

  
  

  • Mid-term Problem Set (25%): A set of roughly 5-6 proof-based exercises  that will be posted at the end of the third week of the classes. Students will have a week  for solving and submitting their solutions.  

  • Final Problem Set (40%): Similar to the Mid-term problem set. This time, the number of the problems will be more, and students will be given one more week. The Final exercises are set to be posted right after the mid-terms are handed in.

  • Scribes (25%): Every student is expected to scribe the notes of at least one lecture note. The LaTeX template will be provided, as well as the scribe notes of the first session as an instance. The notes of every session should be available within one week. You are expected to provide a preliminary draft within the first three days so the instructor can give feedback. Then, you can complete the notes in the next four days and submit the final version. 

  • Weekly Assignments (10%): A set of three or four questions are posted every week. These questions would require you to understand the lecture to answer them. The TA will go over them in the tutorial sessions and discusses the solutions with the students.

  
  

  Tentative Topics

  
  

  1. Introduction, Vertex Cover, TSP
  2. Metric Steiner Trees and Multiway-Cut  
  3. Set Cover, Shortest Super-String
  4. k-Centre Problem and Parameter Pruning
  5. Linear Programming (LP) and Duality Intro
  6. LP-Based Algorithms for Set Cover
  7. Scheduling Jobs on Parallel Machines
  8. Knapsack Problem and Approximation Schemes
  9. Minimum-Degree Spanning Trees via Local Search
  10. Max-SAT and Randomized Rounding
  11. Steiner Forest via Primal-Dual

  
  

  Study Material

  
  

  Books:

  • Approximation Algorithms, Vijay V. Vazirani, Springer-Verlag, Berlin, 2001
  • The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys, Cambridge University Press, 2011.

  
  

  
  

  Similar Courses:

  • Approximation Algorithms, Chandra Chekuri
  • Approximation Algorithms, Zachary Friggstad
  • Approximation Algorithms, Anupam Gupta and R. Ravi
  • Approximation Algorithms and Approximability, Mohammad R. Salavatipour
  • Approximation Algorithms, Joachim Spoerhase

  • 

    Announcements Forum