Approximation Algorithms: Fall 2008

Most of the interesting problems in discrete optimization are known to be NP-hard. Therefore finding an optimal solution may be prohibitively time consuming, following the widely believed conjecture that P &ne NP. When the efficiency of algorithms (polynomial running time) is an important issue, one is willingly to sacrifice the optimality of solutions - up to a certain extent. In the area of approximation algorithms, we design polynomial time algorithms that provide a guaranteed performance on the quality of their solutions.

This course aims to provide a broad introduction into the design and analysis of approximation algorithms. We will focus on fundamental techniques and problems in this area.

Course Contents:

Lectures

Instructors:	Spyros Angelopoulos, Nicole Megow and Rajiv Raman
Time & room:	Tue 12-14 in E1 4 room 024 & Thu 12-14 in E1 3 room 003 The lectures will be from 12:30 to 14:00!
Start:	Tuesday, October 21, 2008
Flyer:	[pdf]
Credit:	This lecture is an advanced course with integrated exercise sessions (3+1). To get a graded certificate (6 CP) we expect you to attend the lectures and exercise sessions regularly. In the exercise sessions we expect you to participate actively and present solutions of at least three homework exercises at the board. In the last week of the term will be an exam.
Prerequisites:	Basic knowledge of algorithms, complexity as well as elementary calculus, linear algebra and probability.
Course Material:	We will follow the book Approximation Algorithms by Vijay Vazirani (Springer, 2001) which will be supplemented with research papers. Other references are Dorit Hochbaum, Approxmiation algorithms for NP-hard problems, PWS Publishing Company, Boston, MA, 1996 Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela und M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, Berlin, 1999.

1. Lecture (21 Oct.): Introduction [pdf], vertex cover, set cover

2. Lecture (23 Oct.): Steiner Tree: approx. factor preserving reduction to Metric ST, 2-approximation, TSP: inapproximability, Christofides' Alg.'s for Metric TSP

3. Lecture (28 Oct.): DP & FPTAS for Knapsack, DP Bin Packing with constant no. of distinct item sizes

4. Lecture (30 Oct.): Bin Packing vs. Min Makespan Scheduling, PTAS Scheduling; on strong NP-hardness, pseudopolyn. algorithms, FPTASes

1. Exercise Session (4 Nov.): Problem set [pdf]

5. Lecture (Nov 6): Introduction to Linear Programming and LP rounding. Notes by Michel Goemans (MIT) [ps]

6. Lecture (Nov 11): Examples of LP Rounding: Vertex Cover, Set Cover. Randomized rounding for Set Cover. (Chapter 14 in textbook [Vaz]).

7. Lecture (Nov 13). A 3/4 approximation algorithm for MAX-SAT (chapter 16 in [Vaz]). Half-integrality of Vertex Cover LP-based solutions (section 14.3). Concentration inequalities: Markov inequality and the Chernoff bound.

8. Lecture (Nov 18). Derandomization of algorithms using conditional probabilities. Introduction to LP-duality (section 12.1 in the textbook). Problem set 2: [pdf]

9. Lecture (Nov 20.) Interpreting the dual LP. The primal-dual method for approximation algorithms. A 2-approximate primal-dual algorithm for Vertex Cover.

10. Problem session 2 (Nov 25). Problem set 3 posted: [pdf]

11 Lecture (Nov 27). A primal-dual algorithm for Steiner Forests.

12 Lecture (Dec 4). Finished the 2-approximation primal-dual algorithm for Steiner Forests. The local search paradigm and a 2-approximation algorithm for MAX-CUT.

13 Problem set 2.

(Dec 11). Started Primal-dual for facility location.

(Dec 16). Finished facility location, and k-median via Lagrangean Relaxation

(dec 18). Lagrangean Relaxation cond., finished budgeted spanning tree using lagrangean relaxation.

(Jan 6). Local search (LS) revisited: facility location.

(Jan 8). Finished LS for facility location. LS for scheduling: move/split. Introduction optimization with incomplete information.

(Jan 13). Stochastic scheduling model, LP-based lower bound.

(Jan 15). LP-based approximation algorithm for non-preemptive. Short Sketch of Gittins Index based lower bound and approximation algorithm for preemptive stochastic scheduling.

Problem set 4: [pdf], due Jan 29. (Changed on Jan 23.)

(Jan 20). Online optimization: competitive analysis, ski rental problem, cow path problem, alpha-list scheduling.

(Jan 22). Semidefinite Programming based approximation algorithms: Goemans-Williamson algorithm for MAX-CUT.

(Jan 27). Exercise session.

(Jan 29). Semidefinite Programming for Graph Coloring. Karger Motwani Sudan.

(Feb 3). Completed the Semidefinite programming based algorithm of KMS for graph coloring.

Problem set 5: [pdf], due Feb 10.

(Feb 5) PCP Theorem and hardness of apprxomations. Hardness of MAX-3-SAT(29)

Approximation Algorithms

Advanced lecture winter 2008/09

Course Contents:

Lectures