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
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.
(due September 15)
Homework 2 (due September 24)
Homework 3 (due October 6)
Homework 4 (due October 13)
Homework 5 (due October 22)
Lectures (Notes scribed by students at the Indian Institute of Science, Bangalore in Fall 2002):
Linear Programming Relaxations:
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
Lecture 20: Solving Semidefinite
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
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:
applied to Facility Location
Dual Fitting applied to Facility Location
A General Approximation Technique For Constrained Forest Problems
LP rounding algorithms for MAX SAT
Approximate max-flow min-(multi)cut theorems and their applications.
3/2 Approximation to Multiway Cut
Papers and Notes for Algorithms Covered in Class:
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.