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