Approximation Algorithms and Hardness of Approximation

Credits 
4 

Lecturers 
Ola Svensson (course responsible) and Alantha Newman 

Schedule 
Tuesdays at 16:1518 and Fridays at 10:1512, 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 socalled hardness of approximation results that are based on the now
famous PCPTheorem. 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.latexproject.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 
1012 
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 
1113 
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 
1618 
February 26 
INM 203 
Sections 8.18.2 and 9 in book
[1]. Sections 3.1 and 3.3 in book [2]. Notes 
Approximation to any degree 
Friday 
1012 
March 1 
INM 203 
Section 11 in book
[1]. Section 10.1 in book [2]. Notes 
Approximation to any degree 
Tuesday 
1618 
March 5 
INM 203 
Continuation of Section 11 in book
[1] and Section 10.1 in book [2]. Notes 
Linear Programming 
Friday 
1012 
March 8 
INM 203 
Chapter 14 in book [1]. Notes

LP extreme point structure 
Tuesday 
1618 
March 12 
INM 203 
Chapter 17 in book [1]. Notes 
LP iterative rounding 
Friday 
1012 
March 15 
INM 203 
Sections 3.13.2 in book [4] Notes

LP iterative rounding 
Tuesday 
1618 
March 19 
INM 203 
Chapter 4 in [4]. Notes 
LP iterative rounding cont. 
Friday 
1012 
March 22 
INM 203 
Chapter 4 in [4]. Notes

Dual fitting 
Tuesday 
1618 
March 26 
INM 203 
Notes 
LP Primal Dual: Facility Location 
Tuesday 
1618 
April 9 
INM 203 
Notes 
Sparsest Cut, Embedding
metrics into L1 
Friday 
1012 
April 12 
INM 203 
Notes

Intro SDP (max cut,
correlation clustering) 
Tuesday 
1618 
April 16 
INM 203 
Notes 
SDP (Graph coloring) 
Friday 
1012 
April 19 
INM 203 
Notes

PCPTheorem 
Tuesday 
1618 
April 23 
INM 203 
Notes, Chapter 22 in [3] 
PCPTheorem 
Friday 
1012 
April 26 
INM 203 
Notes, Chapter 22 in [3]

PCPThm 
Tuesday 
1618 
April 30 
INM 203 
Notes, Chapter 22 in [3] 
PCPThm 
Friday 
1012 
May 3 
INM 203 
Notes,Chapter 22 in [3]

PCPThm, Hardness of Max3SAT 
Tuesday 
1618 
May 7 
INM 203 
Notes, Chapter 22 in [3] 
Hardness of Max3SAT 
Friday 
1012 
May 10 
INM 203 
Notes, Chapter 22 in [3]

Unique Games Conjecture 
Tuesday 
1618 
May 14 
INM 203 
Notes 
Max Cut 
Friday 
1012 
May 17 
INM 203 

Project presentations 
Tuesday 
1618 
May 21 
INM 203 

Project presentations 
Friday 
1012 
May 24 
INM 203 

Project presentations 
Tuesday 
1618 
May 28 
INM 203 

Time to work on bonus points 
Friday 
1012 
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, primaldual 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, Max2Sat.
 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 PCPtheorem
 Tight hardness of Max 3SAT (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: