EO325: Approximation Algorithms
Instructor: Kamesh Munagala
CSA Dept, IISc Bangalore, Spring 2002


Homework 1

Homework 2

Homework 3

Research Problem 1

Research Problem 2

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

Lecture 4: Greedy Algorithms for Makespan

Lecture 5: FPTAS for Knapsack

Lecture 6: PTAS 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

Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.

The space complexity of approximating the frequency moments

Maintaining Stream Statistics over Sliding Windows