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

News

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:

Start by briefly summarizing the main topics discussed in the lecture;
Try to use full sentences/prose - avoid bullet points;
(Very important) Make sure to also include the motivation, illustrative examples and intuitions related to the presented concepts/algorithms/proofs -- either the ones presented in the lecture or (even better!) the ones you came up on your own;
If there is a simple figure that you feel would be helpful in understanding something, try to include it too;
Make sure that all the formal arguments are correct and do not have any gaps in reasoning - if something in the argument is unclear to you, just email the lecturer for clarification.
Polish the language and spell check your notes before sending them to the lecturer;

(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

"Approximation Algorithms" by V. Vazirani (pdf),
"The Design of Approxiation Algorithms" By David P. Williamson and David B. Shmoys (pdf),
"Computational Complexity: A Modern Approach Textbook" by Sanjeev Arora and Boaz Barak (pdf).
"Iterative Methods in Combinatorial Optimization" by Lap Chi Lau, R. Ravi, and Mohit Singh. (pdf)

Assignments

First set of problems which is due March 19.
Second set of problems which is due April 9.
Third set of problems which is due April 30.
Fourth set of problems which is due May 14.
Bonus set of problems which is due June 6. This deadline is hard and no late solutions will be accepted.

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:

Combinatorial Algorithms (greedy algorithms, the local ratio technique). Possible applications: covering, packing, and scheduling problems.
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).
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.
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.
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.
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.
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

Links

Similar courses given previously at other universities: