EO325:
Approximation Algorithms

Instructor: Kamesh
Munagala

CSA Dept,
IISc Bangalore, Spring 2002

Homeworks:

Lecture Notes (scribed by Siddharth Y. R. and Easwaran R.):

Lecture 4: Greedy Algorithms for Makespan

Lecture 7: Euclidean TSP: Karp's Partitioning Scheme

Lecture 8: Karp's Partitioning Scheme: Probabilistic Analysis

Lecture 9: Local Search: The MDST Problem

Lecture 10: Linear Programming: Vertex Cover

Lecture 11: Randomized Rounding: VLSI Layout

Lecture 12: Filtering: Facility Location

Lecture 13: The Minimum Multicut Problem

Lecture 14: The Sparsest Cut Problem

Lecture 15: Balanced Cuts and their Applications

Lecture 16: Primal Dual Method: Vertex Cover

Lecture 17: The Steiner Forest Problem

Lecture 18: Semidefinite Programming: MAX-CUT

Lecture 19: Data Streams: Querying on Windows

Lecture 20: Data Streams: Frequency Moments

Lecture 21: Derandomization: MAX-SAT

Student Presentations:

Lecture 22: Nash Equilibria and Routing (Antara)

Lecture 23: PTAS for Euclidean TSP (Amar)

Lecture 24: Embedding Metrics in Trees (Siddharth)

Lecture 25: L-1 Embeddings and Sparsest Cut (Venkatesh)

Lecture 26: Approximating the Smallest Grammar - I (Easwaran)

Lecture 27: Approximating the Smallest Grammar - II (Rajesh)

Lecture 28: Graph Coloring using Semidefinite Programming (Deepak)

Papers (almost) Covered in Class:

Karp's Partitioning Scheme for Euclidean TSP.

Approximating the Minimum Degree Steiner Tree to Within One of the Optimal.

Approximation algorithms for facility location problems.

Approximate max-flow min-(multi)cut theorems and their applications.

On Reducing the Cut Ratio to the Multicut Problem

A General Approximation Technique For Constrained Forest Problems