Instructor: Kamesh Munagala
CSA Dept, IISc Bangalore, Spring 2002
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
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