CPS 296.04: Approximation Algorithms

Instructor: Kamesh Munagala
 Fall Semester, 2004

Approximation algorithms have become the method of choice for attacking intractable  combinatorial optimization problems.  These algorithms achieve efficient running times, significantly paring down search spaces,  with a mild sacrifice in the quality of the solution found. In the past decade, several elegant general-purpose techniques have been developed for large classes of intractable problems. This course will provide a detailed introduction to these techniques. By the end of this course,  you will know enough to be able to design approximation algorithms yourself, and be an effective researcher in this field. Given the ubiquitous nature of intractable problems across application domains in computer science, you will benefit from this course even if you are a researcher in disciplines such as robotics, computational biology, and systems. I will attempt to provide  "real-world" motivations for the problems considered, as well as the performance  of the algorithms described in practice.

The first part of the course will cover traditional approximation algorithms, with combinatorial and linear programming techniques, with an extended survey of cut problems and metric embeddings. The latter half of the course will cover topics which are only loosely related to approximation -- embeddings, dimensionality reduction, locality sensitive hashing, and game theory.

The textbook for the course is "Approximation Algorithms" by Vijay Vazirani.  Most of the course material can also be found online in the form of papers and lecture notes. I have compiled some links below.


Homework 1    (due September 15)
Homework 2    (due September 24)
Homework 3    (due October 6)
Homework 4    (due October 13)
Homework 5    (due October 22)

I have compiled a list of projects below. Each project has a list of papers (you will have to read some additional papers in the references to get the full context of the problem), as well as a suggested list of open problems. You are free to choose other problems associated with these papers, or other lists of papers and associated problems that you find interesting. Please let me know what you are going to do. You can work in groups of two.

I would suggest spending the first half of the course reading up and understanding the papers, and presenting them in class (around end of October).  Reading up the papers suggested itself is not an easy activity and would require reasonable time and effort, so I will give full credit to a good presentation of them.

Project 1: K-Line Center
Project 2: Oblivious Routing Schemes
Project 3: All or Nothing Multicommodity Flow Problem
Project 4: Maximum Independent Set of Axis Parallel Rectangles
Project 5: Greedy Algorithm for the Steiner Forest Problem

Lectures (Notes scribed by students at the Indian Institute of Science, Bangalore in Fall 2002):

Combinatorial Techniques:

Lecture 1: Lower Bounding Techniques and Metric TSP
Lecture 2: Euclidean TSP: Karp's Partitioning Scheme
Lecture 3: Karp's Partitioning Scheme: Probabilistic Analysis
Lecture 4: FPTAS for Knapsack
Lecture 5: Greedy Algorithms for Makespan

Lecture 6: PTAS for Makespan

Lecture 7: Local Search: The Min Degree Spanning Tree Problem

Linear Programming Relaxations:

Lecture 8: Linear Programming: Vertex Cover
Lecture 9: Randomized Rounding applied to VLSI Layout

Lecture 10: Filtering: Facility Location
Lecture 11: Dual Fitting and the Greedy Set Cover Algorithm
Lecture 12: Primal Dual Method and Vertex Cover
Lecture 13: Primal Dual applied to the Steiner Forest Problem

Cuts, Metrical Relaxations, and Embeddings:

Lecture 14: Basic Embedding Results and Applications
Lecture 15: Tree Embeddings: Buy at Bulk Network Design and
L1 Embeddings

Lecture 16: Min Multicut and Metrical Relaxation for Sparsest Cut

Lecture 17: Rounding for Sparsest Cut via L1

Lecture 18: Balanced Cuts and their Applications

Lecture 19: Tree Embeddings via Random Cuts

Random Hyperplanes, Dimensionality Reduction, and Hashing:

Lecture 20: Solving Semidefinite Programs
Lecture 21: Rounding SDPs using Random Projections: MAX-CUT
Lecture 22: Dimensionality Reduction via Random Projections: J-L Theorem
Lecture 23: Approximate Nearest Neighbors
Lecture 24: Locality Sensitive Hashing: Random Projections and Min Hashing

Game Theory:

Lecture 25: Selfish Algorithmic Strategies
Lecture 26: Cost Sharing Schemes using Primal Dual Algorithms

Related Interesting Papers:

Combinatorial Algorithms:

PTAS for Euclidean TSP
Average Case Analysis of the Nemhauser-Ullman Algorithm for Knapsack

Smoothed Analysis of the Discretization Scheme for Knapsack

Local Search Heuristics for the k-median and Facility Location Problems

Linear Programming Algorithms:

Primal-Dual applied to Facility Location
Dual Fitting applied to Facility Location
A General Approximation Technique For Constrained Forest Problems
LP rounding algorithms for MAX SAT
Bourgain's Theorem
Approximate max-flow min-(multi)cut theorems and their applications.
3/2 Approximation to Multiway Cut

Semidefinite Programming:

Graph Coloring using Semidefinite Programming

Game Theory:

Nash Equilibria and Routing
Primal Dual interpretation of cost sharing schemes
Computing Equilibrium Prices in Markets

Papers and Notes for Algorithms Covered in Class:

Lecture 2, 3: Karp's Partitioning Scheme for Euclidean TSP.
Lecture 7:    Approximating the Minimum Degree Steiner Tree to Within One of the Optimal.
Lecture 9:    Approximation algorithms for facility location problems.

Lecture 12:  A General Approximation Technique For Constrained Forest Problems
Lecture 14:  L-1 Embeddings and Sparsest Cut
Lecture 18:  Embedding Metrics in Trees

Lecture 20:  Maximum Cut and Satisfiability Problems Using SDP.