Princeton University
Computer Science Department

Computer Science 593
Advanced Topics in Theory of Algorithms
Approximation Algorithms

Moses Charikar

Schedule and Readings

Fall 2001
General Information | Schedule and Readings | What's New?


Notes, problems and exercises for the guest lecture on Bin-Packing and Knapsack by Chandra Chekuri.

Slides for the presentation on Multiway Cut by Renato Werneck.

  1. An O(log^*n) Approximation Algorithm for the Asymmetric p-Center Problem
    Rina Panigrahy and Sundar Vishwahnathan,
    Journal of Algorithms 27, 259-268 (1998).

  2. Approximation Algorithms for Directed Steiner Problems
    Moses Charikar, Chandra Chekuri, To-yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha and Ming Li,
    Journal of Algorithms 33, 73-91 (1999).

  3. Local Search Heuristics for k-median and Facility Location Problems (alternate)
    Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala and Vinayaka Pandit,
    in Proceedings of 33rd Annual ACM Symposium on Theory of Computing (STOC) 2001, pages 21-29.

  4. A Constant Factor Approximation for the Single Sink Edge Installation Problem (alternate)
    Sudipto Guha, Adam Meyerson and Kamesh Munagala
    in Proceedings of 33rd Annual ACM Symposium on Theory of Computing (STOC) 2001, pages 383-388.

  5. A polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem (alternate)
    Naveen Garg, Goran Konjevod and R. Ravi,
    in Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 1998, pages 253-259.

  6. An Improved Approximation Algorithm for Multiway Cut
    Gruia Calinescu, Howard Karloff and Yuval Rabani,
    in Journal of Computer and System Sciences, 60(3), pages 564-574 (2000).

  7. Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields
    Jon Kleinberg and Eva Tardos,
    in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 1999, pages 14-23.

  8. Probabilistic Approximation of Metric Spaces and its Algorithmic Applications
    Yair Bartal,
    in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 1996, pages 184-193.

  9. Polynomial Time Approximation Schemes for Geometric k-Clustering.
    Rafi Ostrovsky and Yuval Rabani, in Proceedings of 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2000, pages 349-358.

  10. * A polylogarithmic approximation of the minimum bisection
    Uri Feige and Robert Krauthgamer,
    in Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS) 2000, pages 105-115.

  11. * Approximating the bandwidth via volume respecting embeddings
    Uri Feige,
    Journal of Computer and System Sciences, 60(3), 510-539 (2000).

The last two papers marked with an asterisk (*) are particularly challenging to read and present.


Date Topic Speaker
9/17/01 Introduction: Set Cover Moses
9/24/01 Facility Location and k-Median Moses
10/1/01 Facility Location and k-Median (primal-dual) Moses
10/8/01 Asymmetric p-center (paper 1) Stavros
10/15/01 cancelled due to FOCS'01  
10/17/01 Bin-packing and Knapsack (guest lecture) (exercises) Chandra Chekuri
10/22/01 Metric Methods (multicut, balanced cut) Moses
10/26/01 Probabilistic Approximation of Metric Spaces via Trees Moses
10/29/01 cancelled due to Fall Break  
11/5/01 Local Search for k-Median (paper 3) Amit
11/12/01 Directed Steiner tree (paper 2) Tony
11/19/01 Multiway Cut (paper 6) (slides) Renato
11/26/01 Single Sink Edge Installation (paper 4) Ding
12/3/01 PTAS for geometric k-clustering (paper 9) Manoj
12/10/01 Classification Problems with Pairwise Relationships (paper 7) Adriana