Approximation Algorithms and Hardness of Approximation

Credits 4
Lecturers Ola Svensson (course responsible) and Alantha Newman
Schedule Tuesdays at 16:15-18 and Fridays at 10:15-12, always in INM 203


Bonus assignment is available (hard deadline 23:59 June 6).

Fourth assignment is available (deadline 16:15 May 14).

Third assignment is available (deadline 16:15 April 30).

Second assignment is available (deadline 16:15 April 9).

Project information updated, see here for more information. The deadline of the project is May 28.

First assignment is available. We also prepared a potential schedule for the semester (see below under Schedule and references).

Short description

The goal of this course is twofold. First we aim to learn the powerful techniques used when designing approximation algorithms. Starting with basic techniques such as greedy and dynamic programming algorithms and then moving on to more powerful paradigms including the use and analysis of linear/semidefinite programs. Second we aim to learn the techniques for analyzing our limitations by proving so-called hardness of approximation results that are based on the now famous PCP-Theorem. The techniques for obtaining both kind of results have seen an incredible development during the last decade and we aim to understand them by studying famous applications.

For more details see also the EPFL course book.

Course requirements

The grade will be based on 4 problem sets [60%], scribe notes [20%], and project [20%]. In addition you can positively affect your grade with the bonus assignment. The deadline of the project is May 28. Please see here for more information.

Scribe notes:

For each lecture, there will be one team (of one or two students) in charge of taking detailed notes, typing them in LaTeX, preparing any needed figures, and sending them to the lecturer within at most 72 hours after the lecture. These notes will be posted on the course website.
LaTeX is a typesetting language in which most (if not all) scientific literature is written. So, if you are not familiar with it yet, it is probably a good time to do it now.
To start, take a look at www.latex-project.org and play with our template. (Make sure you have a distribution installed and don't forget to put the preamble.tex and fullpage.sty files in the same directory as the template.)
When preparing scribe notes, please use this template -- just edit it to include your notes. (The template requires preamble.tex and fullpage.sty files to compile. Put them in the same directory.) Here are some guidelines regarding the style of the notes.
The target audience of these notes is you -- students -- a couple of weeks after the lecture, when you already have forgotten what it was about. Therefore, while scribing the notes, you should strive to present, in succinct, readable, and technically correct (but not too formal) way, all the important points and results of the lecture. A couple of more concrete suggestions: (Here is a collection of decent scribe notes (from a different course) that can serve as an example of the expected style and quality.)

Course material

The material of the course will be articles, notes, and parts of the books
  1. "Approximation Algorithms" by V. Vazirani (pdf),
  2. "The Design of Approxiation Algorithms" By David P. Williamson and David B. Shmoys (pdf),
  3. "Computational Complexity: A Modern Approach Textbook" by Sanjeev Arora and Boaz Barak (pdf).
  4. "Iterative Methods in Combinatorial Optimization" by Lap Chi Lau, R. Ravi, and Mohit Singh. (pdf)


Schedule and references

 Introduction Tuesday 10-12 February 19 INF 213  See intro chapters in books [1] and [2]. Also Section 10.1 in book [1] or Section 2.3 in [2]. Notes
 Greedy Algorithms Thursday 11-13 February 21 INF 119 Section 2.1 in book [1] or Section 1.6 in book [2]. Section 2.2 in book [2]. Notes
 Approximation to any degree Tuesday 16-18 February 26 INM 203  Sections 8.1-8.2 and 9 in book [1]. Sections 3.1 and 3.3 in book [2]. Notes
 Approximation to any degree Friday 10-12 March 1 INM 203 Section 11 in book [1]. Section 10.1 in book [2]. Notes
 Approximation to any degree Tuesday 16-18 March 5 INM 203  Continuation of Section 11 in book [1] and Section 10.1 in book [2]. Notes
 Linear Programming Friday 10-12 March 8 INM 203 Chapter 14 in book [1]. Notes
 LP extreme point structure Tuesday 16-18 March 12 INM 203  Chapter 17 in book [1]. Notes
 LP iterative rounding Friday 10-12 March 15 INM 203 Sections 3.1-3.2 in book [4] Notes
 LP iterative rounding Tuesday 16-18 March 19 INM 203  Chapter 4 in [4]. Notes
 LP iterative rounding cont. Friday 10-12 March 22 INM 203 Chapter 4 in [4]. Notes
 Dual fitting Tuesday 16-18 March 26 INM 203  Notes
 LP Primal Dual: Facility Location Tuesday 16-18 April 9 INM 203  Notes
 Sparsest Cut, Embedding metrics into L1 Friday 10-12 April 12 INM 203 Notes
 Intro SDP (max cut, correlation clustering) Tuesday 16-18 April 16 INM 203  Notes
 SDP (Graph coloring) Friday 10-12 April 19 INM 203 Notes
 PCP-Theorem Tuesday 16-18 April 23 INM 203  Notes, Chapter 22 in [3]
 PCP-Theorem Friday 10-12 April 26 INM 203 Notes, Chapter 22 in [3]
 PCP-Thm Tuesday 16-18 April 30 INM 203  Notes, Chapter 22 in [3]
 PCP-Thm Friday 10-12 May 3 INM 203 Notes,Chapter 22 in [3]
 PCP-Thm, Hardness of Max-3SAT Tuesday 16-18 May 7 INM 203  Notes, Chapter 22 in [3]
 Hardness of Max-3SAT Friday 10-12 May 10 INM 203 Notes, Chapter 22 in [3]
 Unique Games Conjecture Tuesday 16-18 May 14 INM 203  Notes
 Max Cut Friday 10-12 May 17 INM 203
 Project presentations Tuesday 16-18 May 21 INM 203 
 Project presentations Friday 10-12 May 24 INM 203
 Project presentations Tuesday 16-18 May 28 INM 203 
 Time to work on bonus points Friday 10-12 May 31 -

Potential topics

The exact topics to be covered will depend on our interests but a set of possibilities includes:
  1. Combinatorial Algorithms (greedy algorithms, the local ratio technique). Possible applications: covering, packing, and scheduling problems.
  2. Approximation to any degree: Some problems, such as Knapsack and Euclidean TSP allows for arbitrarily good approximation if we are willing to spend more time (a so called PTAS or FPTAS).
  3. Linear Programming (randomized rounding, extreme point structure, primal-dual schema, iterative rounding). Examples of applications: Set cover, vertex cover, TSP, assignment problems, facility location, Steiner tree, degree bounded spanning trees.
  4. Semidefinite Programming (hyperplane rounding). Most successful technique for problems with "soft" constraints, which may be violated by paying some additional costs. Examples of applications: Max Cut, Max-2-Sat.
  5. Linear/Semidefinite Programming Hierarchies: Automatic ways of strengthening algorithms. Many new results based on the power of these methods that indicate further interesting developments. Example of application: Max Bisection.
  6. Hardness of approximation:
    • Dinur's proof of the PCP-theorem
    • Tight hardness of Max 3-SAT (how to verify a proof by reading 3 bits)
    • Unique Games Conjecture and its applications. For example, tight hardness of Max Cut and Vertex Cover.
  7. Recent exciting developments:
    • Better algorithms for asymmetric and symmetric TSP
    • The use of hierarchies for constraint satisfaction problems
    • Constructive discrepancy results
    • Improved algorithm for bin packing


Similar courses given previously at other universities: