References
We will be teaching materials from multiple books/sources. Some of them are the following.
- [WS] The Design of Approximation Algorithms, by David Williamson and David Shmoys, Cambridge University Press, 2011.
- [VV] Approximation Algorithms, by Vijay Vazirani, Springer-Verlag, 2004.
- Approximation Algorithms for NP-hard Problems, edited by Dorit S. Hochbaum, PWS Publishing Company, 1995.
- Geometric Approximation Algorithms, by Sariel Har-Peled, American Mathematical Society, 2011
- Complexity and Approximation, by Ausiello et al., 1999
- [LRS] Iterative Methods in Combinatorial Optimization, by Lau, Ravi and Singh.
- A compendium of NP optimization problems.
Similar courses elsewhere:
- Coursera Course: part1, part2, by Claire Mathieu.
- Coursera Course: videos, by Mark De Berg.
- UIUC, 2021: by Chandra Chekuri.
- EPFL, 2013: by Ola Svensson.
- EPFL, 2010: by Thomas Rothvoss.
- CMU, 2005: by Anupam Gupta and R. Ravi.
- CMU, 2008: by Anupam Gupta and Ryan O'Donnell.
- Wisconsin, 2019: by Shuchi Chawla.
- IIT Delhi: by Naveen Garg.
- IIT Delhi: by Amit Kumar.
- Duke, 2017: by Debamalya Panigrahi.
- Duke, 2004: by Kamesh Munagala.
- TUM, 2016: by Susanne Albers.
- Dartmouth, 2019: by Deeparnab Chakrabarty.
- Stanford: 2016: by Amin Saberi.
- Stanford: 1990s: by Rajeev Motwani.
Related other intertesting courses:
Assignments
Scribe Templates
Project Topics
For projects you need to select a project topic from the list given below.
Some reference papers are given below.
You are expected to do a survey of the results and techniques in the topic area.
You can form a group of two students and send the project topic and group details
by 10th February.
You need to submit the final report by the last_day_of_class.
Finally, you need to make a presentation on the topic sometime in mid-April.
- Asymmetric Traveling Salesman Problem
- Metric Traveling Salesman Problem
- Tree Augmentation Problem
- Maximum Independent Set of rectangles
- Packing of convex polygons
- SumOfSquares/LP/SDP Hierarchies
- Unique Games Conjecture
- Inapproximability of Clustering
- Multiway Cut
- Weighted Flow Time
- Geometric Set Cover
- FPT Approximation
- Precedence-constrained scheduling
- CSP
- Explainable k-means
- Approximating Edit Distance
- Approximating Longest Common Subsequence (LCS)
- Approximating Longest Increasing Subsequence (LIS)
- Coreset and Clustering
- Approximating Subset-sum
- Rank Aggregration
Intended audience: Graduate students in computer science,
and mathematics with theoretical interests.
Interested undergraduate students with very strong mathematical
skills.
Prerequisites: Mathematical maturity and a solid background in math
(elementary combinatorics, graph theory, discrete probability, algebra, calculus)
and theoretical computer science (big-O/Omega/Theta, P/NP, basic fundamental algorithms).
Grading: 30% HW, 15% project, 5% Scribes, 20% midterm, 30% final.
Prepared and Maintained by Arindam Khan