E0 249: Approximation Algorithms, Spring 2022

Instructors: Arindam Khan and Anand Louis

TA: Arka Ray

Time: Mon-Wed 3:30 pm-5:00 pm (changed from previous time:Tue-Thu 11:30am-1:00pm), Initially Online (Teams).

Course Description

Tentative Topics:
Basics and definitions related to Approximation Algorithms; Greedy Algorithms (Set cover and Vertex Cover); Combinatorial Algorithms (Traveling Salesman Problem and Steiner Tree); Dynamic Programming and Rounding (Knapsack and Bin Packing); LP-based Algorithms: Randomized and Deterministic Rounding, Dual-Fitting, Primal-Dual Schema; Cuts and Metrics (Multicut, Multiway Cut, Max Cut, Sparsest Cut); SDP (Max Cut and Coloring); Geometric Approximation Algorithms (Geometric Set Cover, Hitting Set, Independent Set of Rectangles): Greedy, Shifted-Grid, Quad-Trees, Geometric Separators, Local Search; Sum of Squares; Hardness.

---

Lectures

Tentative schedule: (subject to change)
• Jan 4-6 (Week 1 - Arindam): Introduction; Greedy Algorithm: Set Cover, Vertex Cover; Local Search: Max-Cut. (Scribe)
  • Source: VV Ch 1, 2; WS Ch 1.1, 1.6.
  • Videos: Intro, Set Cover, Max Cut.
  • Handwritten notes: 1st class, 2nd class
  • Other interesting links: Graham's 1966 paper, Tight analysis for greedy algorithm for set cover.
  
  
• Jan 11-13 (Week 2 - Arindam): Combinatorial Algorithms: Traveling Salesman Problem, Steiner Tree; Dynamic Programming and Rounding: Knapsack and Bin Packing. (Scribe)
  • Source: VV Ch 3, 8, 9; WS Ch 2, 3.
  • Videos: TSP, Knapsack, Bin Packing.
  • Handwritten notes: Week 2.
  • Other interesting links: Christofides paper, Greedy Algorithms for TSP, Book on TSP, Book on Steiner Tree, Book on Knapsack, Survey on Multidimensional Bin Packing, Fun Video (Steiner Tree using Soap)
  • Present Best Approximation Algorithms: Metric TSP (2021), Steiner Tree (2013), Knapsack (2019), Bin Packing (2015).
  
  
• Jan 17-19 (Week 3 - Arindam): Introduction to Linear Programming, LP Duality. (Scribe)
  • Source: Tim Toughgarden's Lecture Notes from A Second Course in Algorithms (see [TN] for links to pdfs), Videos: part 1, part 2, part 3, part 4
  Also: VV Ch 12; WS Ch 1.2-1.7, Appendix A; LRS Ch 2; Videos on Basic Feasible Solutions: part 1, part2.
  • Videos: Intro to LP, LP Duality, Max Flow Min Cut, Algorithms for LP, Extreme Point Solutions.
  • Handwritten notes: Week 3.
  • Advanced Resources on LP: Theory of Linear and Integer Programming (by Schrijver)[Highly recommended], Linear Programming: 2: Theory and Extensions (By Dantzig and Thapa) (Gives a comprehensive survey of simplex and interior-points), Book on LP by Karloff, Grotschel-Lovasz-Schrijver Book (For Ellipsoid Methods and Separation Oracle), Interior Point Methods for Optimizaton (By Roos, Terlaky, Vial), Interior Point Algorithms (Book by Yinyu Ye), Book on Interior-point by Nesterov and Nemrovski (covers extensive and advanced topics on Interior-points).
  • Other interesting links: Integrality of polyhedra, Algorithms for Convex Optimization (By Nisheeth Vishnoi), LP/SDP Hierarchies (Monograph by Thomas Rothvoss), Lau-Ravi-Singh Book on Iterative Methods .
  
  
• Jan 24-26 (Week 4 - Arindam): LP-based Algorithms: Randomized and Deterministic Rounding, Dual Fitting, Primal-Dual Schema. (Scribe)
  • Source: VV Ch 13, 14, 15; WS Ch 4, 5, 7.
  • Videos: Deterministic Rounding, Randomized Rounding, Primal-Dual Schema, Dual Fitting.
  • Handwritten notes: Week 4.
  • More on LP Rounding: Randomized Rounding Survey, Dependent Rounding Survey, Iterative Rounding.
  • More on Primal Dual: Goemans-Williamson Survey (For Network Design) , Survey by Williamson , Buchbinder-Naor Survey (For Online Algorithms), Naor's Talk at Simons , Nikhil Bansal's Talk .
  • More on Dual-Fitting and Factor Revealing LPs: Borodin's Lecture , Greedy Facility Location using Dual-Fitting and Factor-Revealing LP , Factor-Revealing LP in Online Matching (Ranking), Dual-Fitting for Online Scheduling.
  • Other Links: Survey on Local Ratio, Survey on Local Search.
  
  
• Jan 31-Feb 2 (Week 5 - Anand): Min s-t cut and Multiway cut. (Scribe (part1), Scribe (part2))
  • Source: VV Ch 4, 19; WS Ch 8.
  • Slides: Week 5.
  • Other Links: 1.297 approximation for multiway cut[Sharma, Vondrak '14]., Integrality gap of multiway cut LP > 1.2.
  
  
• Feb 7-9 (Week 6 - Anand): Sparsest cut (Metric embedding, Bourgain's Theorem, Expander). (Scribe)
  • Source: VV Ch 21; WS Ch 15.
  • Slides: Week 6.
  • Other Links: Lecture Notes on Graph Partitioning, Expanders and Spectral Methods [By Luca Trevisan], Geometry, Flows, and Graph-Partitioning Algorithms [By Arora, Rao, Vazirani].
  
  
• Feb 14-16 (Week 7 - Anand) SDP (Maxcut and Coloring) (Scribe (part1), Scribe (part2))
  • Source: VV Ch 26; WS Ch 6.
  • Slides: MaxCut, Coloring.
  • Other Links: KKMO'05 paper (Optimal inapproximability for MaxCut and Max2SAT under UGC), Raghavendra'08 paper (Optimal algorithms and inapproximability results under UGC for every CSP), Raghavendra-Steurer'10 paper, Kawarabayashi-Thorup'17 paper (n^0.19996 coloring for 3 colorable graphs).
  
  
• Feb 19 (Sat): Midterm.


• Feb 21-23 (Week 8 - Anand): Beyond Worst Case Ananlysis, and SAT (Scribe (part1), Scribe (part2))
  • Source: VV Ch 16; WS Ch 5.
  • Slides: Beyond Worst Case Analysis, SAT.
  • Other Links: Roughgarden book on Beyond Worst-Case Analysis, Hardness of 7/8 for Max3SAT [by Hastad'99].
  
  
• Feb 28- Mar 2 (Week 9 - Arindam): Geometric Approximation: geometric intersection graph, geometric set cover, hitting set, independent set of rectangles. Techniques: greedy, shifted grid, quad-trees. (Scribe)
  • Videos: Greedy, Shifted Grid, Quadtree, Guillotine.
  • Handwritten Notes: Week 9.
  • Sources: Hochbaum-Maass'85 (Shifted Grid), Erlebach-Jansen-Siedel'01 (Shifted Hierarchical Decomposition), Chan'03 (Shifted Quadtrees).
  • Other links: Smith-Wormald'98, Guillotine cutting of rectangles , Galvez et al. '22 (2+eps apprpximation algorithm for MISR).
  • Talks: O(1)-approximation for MISR by Mitchell , 2+eps approximation algorithm for MISR: part 1, part 2.
  
  
• Mar 7-9 (Week 10- Arindam): Geometric Approximation: Techniques: geometric separators, local search, LP. (Scribe)
  • Videos: Geometric Separator, Local Search, MWISR O(log log n)-approx (part1), MWISR O(log log n)-approx (part2).
  • Handwritten Notes: Week 10.
  • Sources: Chan'03 (separator for overlapping fat objects), Fox-Pach'11, Chan-Har peled'09 (Local Search), Chalermsook-Walczak'21 (MWISR loglogn approx) .
  • Other Links: Chi-boundedness Survey[by Scott-Seymour], Planar Separator Theorem Proof(By Har-Peled), Geometric Separator by Fox-Pach, QPTAS for MISR.
  
  
• Mar 14-16 (Week 11 - Arindam): Geometric Approximation:VC-dimension, Epsilon-nets; Geometric Packing: Shifting, Guessing, NFDH. (Scribe)
  • Videos: Set Cover with bounded VC-dimensions, Geometric Packing.
  • Handwritten Notes: Week 11.
  • Sources: Ch 5,6 from Har-Peled Book, Bronniman-Goodrich'95 paper, Even et al.'05.
  • Other Links: Aronov-Ezra-Shamir'10 (O(log log n)-approximation for geometric set cover), NFDH and simple shelf packing[By Coffman et al.,'80], APTAS for 2D bin packing with squares [By Jansen-SolisOba'08], PTAS for 2D knapsack with squares[By Bansal et al., '06], Perfect Packing of Squares [by Terence Tao'22].
  
  
• March 21-23(Week 12 - Anand): Facility Location. (Scribe)
  • Slides: Week 11.
  • Sources: WS Ch 4.5, 5.8.
  • Other Links: Li [ICALP'11] (1.488 approximation for facility location), Guha-Khuller'99 (No < 1.463 approximation).
  
  
• March 28-30 (Week 13 - Anand): Primal-Dual for Facility Location, Local Search for k-Median. (Scribe)
  • Slides: Primal-Dual for FL, Local Search for k-Median.
  • Sources: WS Ch 7.3, 7.6, 9.2.
  • Other Links: Byrka et al. ['17] (present best 2.675 approximation for k-median).
  
  
• April 4-6 (Week 14 - Anand): PCP, Unique Games, Small Set Expansion, 2-to-2 games, subexponential algorithm for UG. (Scribe (part1), Scribe (part2))
  • Slides: Week 14.
  • Sources: Survey on Unique Games.
  • Other Links: 2-to-2 Games, Quanta article.
  
  

April 10-11: Presentations.


Important Dates:
Course Drop Deadline without mention: 1st March, 2022
Course Drop Deadline with mention: 1st April, 2022
Last date for instruction: 12th April, 2022.
Course and Instructor Feedback: 5-17 April, 2022.
Final: 20 April, 2022 (2pm-5pm, Open book/notes)

---

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:
• [TN] Linear Programming: part 1, part 2, part 3, part 4, by Tim Roughgarden.
• The Lasserre hierarchy in Approximation algorithms: by Thomas Rothvoss.
• UIUC, 2018: Geometric Approximation Algorithms, by Timothy Chan.
• UW, 2005: PCP Theorem and Hardness of Approximation, by Venkat Guruswamy and Ryan O'Donnell.




---

Assignments

• HW 1
• HW 2
• HW 3
• HW 4
• HW 5
• HW 6

---

Scribe Templates

• preamble.tex, lect01.tex
• Overleaf: Learn LaTex
• MIT: Intro to LaTex
• Evan Chen's LaTex hacks
• TikZ package for drawing




---

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.


1. Asymmetric Traveling Salesman Problem
• An improved approximation algorithm for ATSP. Traub-Vygen (STOC'20) .
• A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Svensson et al.(STOC'18) .


2. Metric Traveling Salesman Problem
• A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP, Karlin et al. .
• A (Slightly) Improved Approximation Algorithm for Metric TSP. Karlin et al. (STOC'21) .


3. Tree Augmentation Problem
• A Better-Than-2 Approximation for Weighted Tree Augmentation. Traub-Zenklusen (FOCS'21) .
• Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches. Cecchetto et al. (STOC'21) .


4. Maximum Independent Set of rectangles
• A (2 + ε)-Approximation Algorithm for Maximum Independent Set of Rectangles. Galvez et al. (SODA'22) .
• Approximating Maximum Independent Set for Rectangles in the Plane. Mitchell, (FOCS'21) .


5. Packing of convex polygons
• On the Two-Dimensional Knapsack Problem for Convex Polygons. Merino-Wiese, ICALP'20) .
• Online Sorting and Translational Packing of Convex Polygons. Aamand et al., 2021) .


6. SumOfSquares/LP/SDP Hierarchies
• Course by Barak and Steurer.
• Rothvoss Survey.
• CWI Reading Group.


7. Unique Games Conjecture
• Towards a Proof of the 2-to-1 Games Conjecture? Dinur et al., STOC'18.
• UGC Survey.


8. Inapproximability of Clustering
• Inapproximability of k-means and k-median in Lp-metrics. Cohen-Addad et al., (SODA'22) .
• Inapproximability of Clustering in Lp-metrics. Cohen-Addad et al., (FOCS'19) .


9. Multiway Cut
• Simplex Transformations and the Multiway Cut Problem. Buchbinder et al., Math. Oper. Res., 2021.
• Multiway cut, pairwise realizable distributions, and descending thresholds, Sharma et al., STOC'14.


10. Weighted Flow Time
• A (2 + ε)-approximation algorithm for preemptive weighted flow time on a single machine. Rohwedder and Wiese, STOC'21..
• A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time, Feige et al., SODA'19.


11. Geometric Set Cover
• Non-uniform Geometric Set Cover and Scheduling on Multiple Machines, Bansal et al., SODA'21.
• The Geometry of Scheduling, Bansal et al., SICOMP'14.


12. FPT Approximation
• A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms, Feldmann et al.
• FPT-approximation for FPT Problems, Lokshtanov et al., SODA'21.
• A Parameterized Approximation Scheme for Min k-Cut, Lokshtanov et al., FOCS'20.


13. Precedence-constrained scheduling
• Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time, Garg et al., SODA'19.
• A (1+ε)-approximation for makespan scheduling with precedence constraints using LP hierarchies, Levey and Rothvoss, STOC'16.


14. CSP
• Approximating Constraint Satisfaction Problems on High-Dimensional Expanders, Alev et al.


15. Explainable k-means
• Explainable k-Means and k-Medians Clustering, Dasgupta et al. .
• Explainable k-means. Don't be greedy, plant bigger trees!, Makarychev et al. .
• Near-optimal Algorithms for Explainable k-Medians and k-Means, Makarychev et al..


16. Approximating Edit Distance
• Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time, Chakraborty et al. [FOCS'18] .
• Edit Distance in Near-Linear Time: it's a Constant Factor, Andoni et al. [FOCS'20] .


17. Approximating Longest Common Subsequence (LCS)
• Approximating LCS in Linear Time, Hijiaghayi et al., [SODA'19] .
• Approximation Algorithms for LCS and LIS with Truly Improved Running Times, Rubinstein et al., [FOCS'19] .


18. Approximating Longest Increasing Subsequence (LIS)
• Estimating the longest increasing sequence in polylogarithmic time, Saks and Sheshadhri [FOCS'10] .
• Improved Sublinear Time Algorithm for Longest Increasing Subsequence, Mitzenmacher et al. [SODA'21] .


19. Coreset and Clustering
• Chen [SICOMP'19] .
• A Unified Framework for Approximating and Clustering Data, Feldman and Langberg .
• A New Coreset Framework for Clustering, Cohen-Adda et al. .


20. Approximating Subset-sum
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum, Bringmann. .
• A Fine-Grained Perspective on Approximating Subset Sum and Partition, Bringmann et al. .


21. Rank Aggregration
• Approximating the Median under the Ulam Metric, Chakraborty et al. [SODA'21] .
• Chapter 7 of thesis of Warren Schudy. .




---

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

---