MS&E 319: Approximation Algorithms
Administrative Information
- Instructor: Amin Saberi (Office Hours: by appointment)
- Lectures: Monday – Wednesday 2:15 pm– 3:30 pm at 540-103
- Course assistant: Vahideh Manshadi (Office hours: Wednesday 12:30 pm – 2 pm at Huang Engineering, Room 16)
Text book: Some of the lectures and exercises are taken from:
- Approximation Algorithms, by Vijay V. Vazirani, Springer-Verlag, Berlin, 2001.
- The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys, Cambridge University Press, New York, NY, USA, 2011.
Description: This course is on special topics in approximation algorithms with an emphasis on network optimization. The length and
selection of topics will depend on the
interest and enthusiasm of the students and the instructor. We will consider that a feature.
Topics:
Lecture 1 & 2 : Primal-dual framework, Set cover (primal-dual and dual fitting algorithms),
Facility location (primal-dual and dual fitting,
factor revealing linear programs), Steiner Forest
References:
- Chapters 12, 13, 15, and 24 of Vazirani’s book
- K. Jain, M. Mahdian, E. Markakis , A. Saberi, and V. Vazirani, A Greedy Facility Location Algorithm Analyzed using Dual-Fitting with Factor-revealing LP, Journal of the ACM, 2003.
- M.X. Goemans and D.P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, 1995.
Lecture 3 (taught by Luca Trevisan): Approximating sparsest cut spectrally, Cheeger's inequality
References: Luca's lecture notes
Lecture 4 & 5: An O(log n) approximation algorithm for
sparsest cut, Relation to multicommodity flow
LP and metric embedding, Frechet embeddings
and embedding metrics into l1 metrics, Applications
to minimum cut linear arrangement and balanced cut
References:
- Chapter 21 of Vazirani’s book
- P. Indyk and J. Matousek, Low-Distortion Embeddings of Finite Metric Spaces, in Handbook of Discrete and Computational Geometry, 2004.
Lecture 6: Probabilistic approximation of metrics by tree metrics
References:
- J. Fakcharoenphol, S. Rao and K. Talwar, A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics, STOC, 2003.
- Chapter 8 of Williamson-Shmoys’s book
Lecture 7&8: Applications of tree metrics: bandwidth minimization (linear arrangement), oblivious routing, and minimum bisection problem
References:
- Chapter 8.7 of Williamson-Shmoys’s book
- Chapter 15.2 and 15.3 of Williamson-Shmoys’s book
- H. Räcke, Optimal Hierarchical Decompositions for Congestion Minimization in Networks, STOC, 2008.
Lecture 9: Semi-definite Programing, max-cut, and quadratic programing
References:
- Chapter 26 Vazirani’s book
- M.X. Goemans and D.P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, Journal
of the ACM, 1995.
- Chapter 6.3 of Williamson-Shmoys’s book
- Y. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, 1998.
Lecture 10: An O(\sqrt{log(n)}) approximation algorithm for the sparsest cut problem
References:
- S. Arora, S. Rao, and U. Vazirani, Expander Flows, Geometric Embeddings and Graph Partitioning, STOC, 2004
- Chapter 15.4 of Williamson-Shmoys’s book
- S. Arora, J. R. Lee, and A. Naor , Euclidean distortion and the Sparsest Cut, Journal of the American Mathematical Society 21, 2008.
- S. Arora, J. R. Lee, and A. Naor, Frechet embeddings of negative type metrics, Discrete and Computational Geometry 38, 2007.
Lecture 11: Asymmetric Traveling Salesman Problem (ATSP), thin trees, and Goodyn’s conjecture
References:
- M. Held and R. Karp. The traveling salesman problem and minimum spanning trees. Operations Research,1970.
- A. Asadpour, M. Goemans, A. Madry, S. Oveis Gharan, A. Saberi, An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem, SODA 2010.
- L. A. Goddyn. Some open problems i like. Available at: http://people.math.sfu.ca/~goddyn/Problems/problems.html
Lecture 12 & 13: Sampling thin trees using maximum entropy sampling
References:
- A. Asadpour, M. Goemans, A. Madry, S. Oveis Gharan, A. Saberi, An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem, SODA 2010.
Lecture 14: (taught by Jon Vondrak) Dependent randomized rounding
References:
- C. Chekuri, J. Vondrak, R. Zenklusen, Dependent randomized rounding via exchange properties of combinatorial structures, FOCS 2010
Lecture 15 & 16: Traveling Salesman Problem (TSP)
References:
- S. Oveis Gharan, A. Saberi, M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem.
- A. A. Benczur, Cut structures and randomized algorithms in edge-connectivity problems, PhD thesis, 1997.
- T. Fleiner and A. Frank. A quick proof for the cactus representation of mincuts, 2009.
Homeworks:
1. HW#1 Due date: May/05/11