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.
Homeworks:
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)
Lectures
(Notes
scribed by
students at the Indian
Institute of Science,
Bangalore in Fall 2002):
Combinatorial Techniques:
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 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
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
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.