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)

Projects:

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

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 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

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 Embeddings

Lecture 18: Balanced Cuts and their Applications

Lecture 19: Tree Embeddings via Random Cuts

Random Hyperplanes,
Dimensionality Reduction, and Hashing: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 Embeddings

Lecture 18: Balanced Cuts and their Applications

Lecture 19: Tree Embeddings via Random Cuts

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

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

Nash Equilibria and Routing

Primal Dual interpretation of cost sharing schemes

Computing Equilibrium Prices in Markets

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.