Instructor: Barna Saha
Office Hour: After class and by appointment.
The area of approximation algorithms was traditionally designed to come up with polynomial time algorithms for NP-Hard problems by allowing returning approximate solutions. With the advent of Big Data area, the need for approximation algorithms goes far beyond of tackling NP Hard problems. We may need approximation algorithms even for polynomial time problems to allow for faster running time, improved space complexity and changing data. This course will cover some of the new emergent areas of approximation algorithms. The course topics are subject to change with each offering.
Following is a list of tentative topics for this semester.
- Traditional Theory of Approximation Algorithms
- Fine-Grained Approximation Algorithms
- Dynamic/Online Algorithms
- Conditional Hardness & Hardness of Approximation
Time & Venue: The course will meet every Monday and Wednesday from 9:00 am to 10:00 am at Dwinelle 109.
Grading: Each student will be required to scribe one/two lecture notes, present one paper and do a research project individually or in a group of two. There will be one/two problems given every alternate weeks to help better understand the material. They will be peer-graded and due at the end of the semester. Students are allowed to discuss among themselves but must write their own solution.
Writing lecture notes and class participation account for 10% of the grade, the problem set accounts for 15%, the paper presentations account for 25% of the grade and the project accounts for 50%. Project will have several components: (i) project proposal (less than 1 pg) due on Oct 13, (iii) in-class presentation during the last two weeks of the class, and (iv) a final project report (less than 10 pgs) due on Dec 2.
Books: There is no required textbook. Following will be used for reference in the first part of the course.
- The Design of Approximation Algorithms, David Williamson & David Shmoys.
- Approximation Algorithms, Vijay Vazirani.
Prerequisite: Students must have taken one graduate level courses on algorithms or combinatorial optimization such as IND ENG 269, IND ENG 266, IND ENG 262A, CS 270 and CS 271. If you do not satisfy the prerequisite but want to take the course, please talk to the instructor.
Goal: The goal of the course is to make students enough interested in the course topics to do further exploration.
A tentative schedule is below.
| Date | Topic | Notes |
| Aug 28 | Overview of the course. Hard vs Easy. Introduction to Approximation Algorithms. MAX-SAT via Linear Programming Rounding. 3/4 approximation for MAX SAT. | Chapter 1, Chapter 5 of Williamson-Shmoys. Course note from Goeman’s class. Lecture note available on piazza. Further References: 1. On the Approximation of Maximum Satisfiability, M. Yannakakis, SODA 1992. 2. Randomized Variants of Johnson’s Algorithm for MAX-SAT, M. Poloczek, G. Schnitger, SODA 2011. 3. Simple 3/4-approximation algorithm for MAX-SAT, WAOA 2011. 4. A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, N. Buchbinder, M. Feldman, J. Naor, R. Schwartz, FOCS 2012. Announcement: Sign up for piazza (link sent via email) for class related discussions. |
| Sept 4 | Derandomization via the Method of Conditional Expectation, Covering Problems: Set Cover, Vertex Cover. | Chapter 1 of Williamson-Shmoys, Chapter 13 of Vazirani. Chapter 5 of Williamson-Shmoys. Lecture note available on piazza. |
| Sept 9 | Set Cover continued. Introduction to LP Duality, Primal Dual, Greedy, Dual Fitting. | Chapter 1 of Williamson-Shmoys, Chapter 12 and 13 of Vazirani. Announcement: Reading list announced. Check piazza. Lecture note available on piazza. |
| Sept 11 | Submodular Optimization: Submodular maximization: Greedy and Local Search. | Lecture note available on piazza. A pretty extensive coverage of the development in submodular optimization modulo very recent advances. https://www.openu.ac.il/personal_sites/moran-feldman/publications/Handbook2018.pdf Notes: See J. Vondrak’s tutorial. https://theory.stanford.edu/~jvondrak/data/submod-tutorial-1.pdf Notes on submodular function maximization. http://swoh.web.engr.illinois.edu/courses/ie512/handout/submodular.pdf References: An Analysis of Approximations for Maximizing Submodular Set Functions, Nemhauser, Wolsey, Fisher, Mathematical Programming, 1978. Maximizing Non-monotone Submodular Functions, Feige, Mirrokni, Vondrak, FOCS 2007. Submodular Function Minimization under Covering Constraints, S. Iwata, K. Nagano, FOCS 2009. |
| Sept 16 –18 | Continuous Extensions of Submodular Functions Submodular Covering Problems | Lecture note available on piazza. Continuous extensions of submodular functions. https://theory.stanford.edu/~jvondrak/MATH233B-2017/lec15.pdf Lovasz extension and connection to Edmond’s greedy algorithm (also many nice examples of submodular functions in practice) http://people.csail.mit.edu/stefje/mlss/kyoto_mlss_lecture1.pdf |
| Sept 23 | Deterministic and Randomized rounding of linear programs: The uncapacitated facility location problem. | Chapter 4.5 of Williamson-Shmoys. Chapter 5.8 of Williamson-Shmoys. |
| Sept 25 | The Metric Uncapacitated Facility Location Continued. More Randomized Rounding & Primal-Dual | Chapter 7.6 of Williamson-Shmoys Chapter 12.1 of Williamson-Shmoys |
| Sept 30-Oct 2 | More Primal Dual: The Generalized Steiner Tree Problem | Chapter 7 of Williamson-Shmoys |
| Oct 7-21 | Cuts & Metrics Multiway Cut Multicut Probabilistic Embedding on Tree Metric with Applications | Chapter 8 of Williamson-Shmoys Notes on Ellipsoid algorithm |
| Oct 28 | Semi-definite programming rounding. MAX CUT, MAX-2SAT | Chapter 6 of Williamson-Shmoys |
| Nov 4 | Local Ratio | Guest Lecturer: Seri Khoury http://www.cs.tau.ac.il/~azar/Methods-Class10.pdf Maximum Independent Set via local ratio https://dl.acm.org/citation.cfm?doid=3087801.3087806 |
| Nov 6 | Evening Presentation: Dependent Rounding Semi-definitie programming rounding for MAX-SAT More on Submodular Maximization | Dependent Rounding and Its Applications to Approximation Algorithms https://www.cs.umd.edu/~samir/grant/jacm06.pdf A 7/8-Approximation Algorithm for MAX 3SAT http://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satu.pdf A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization https://theory.epfl.ch/moranfe/Publications/FOCS2012.pdf |
| Nov 6 | Hardness of approximation: Approximation Preserving Reductions | Chapter 10 of Williamson-Shmoys. |
| Nov 13 | A fine-grained approach to hardness: ETH, SETH, OV. SETH to OV, Sparsification lemma. | Reference: https://people.csail.mit.edu/virgi/6.s078/ http://web.stanford.edu/class/cs354/scribe/lecture17.pdf [ETH, SETH, Reduction of k-SAT to OV] Proof of the Sparsification lemma https://www.mimuw.edu.pl/~malcin/dydaktyka/2012-13/fpt/fpt_13_eth.pdf |
| Nov 13 | Evening Presentation Computing Edit Distance Fast | References: Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time https://arxiv.org/abs/1810.03664 Constant-factor approximation of near-linear edit distance in near-linear time https://arxiv.org/abs/1904.05390 |
| Nov 18 | OV to Sequence Alignment Problems: Edit Distance. | References: https://arxiv.org/abs/1412.0348 https://arxiv.org/abs/1501.07053 |
| Nov 18 | Presentation: Faster Approximation of the Longest Common Subsequence Problem. Computing CFG parsing fast. | References: Reducing approximate Longest Common Subsequence to approximate Edit Distance https://arxiv.org/abs/1904.05451 General context-free recognition in less than cubic time http://theory.stanford.edu/~virgi/cs367/papers/valiantcfg.pdf |
| Nov 20 | Distributed PCP for Hardness of Approximation in P. | Guest Lecturer: Karthik C.S. |
| Nov 20 | Evening Presentation: Approximating APSP. Speeding up Linear Programming | |
| Nov 25 | APSP, (min,+) matrix multiplication and Equivalences | References: https://people.csail.mit.edu/rrw/tria-mmult.pdf |
| Nov 27 | Fast Algorithm for APSP in non-uniform model. | References: https://people.csail.mit.edu/virgi/6.s078/lec12-LDTs.txt |
| Dec 2nd | Fast Approximation Algorithms for APSP. | References: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.4076&rep=rep1&type=pdf |
| Dec 4th | Fast Exact Algorithm for (min,+) matrix multiplication on Lipschitz matrices. | References: https://arxiv.org/abs/1707.05095 |
| Extra Topics | Dynamic Problems & Hardness | Reference: https://people.csail.mit.edu/virgi/6.s078/lec14-dynamic.pdf |
| Extra Topics | Dynamic Algorithms: design of dynamic algorithms via primal-dual | Reference: https://arxiv.org/abs/1604.05337 |
| Dec 4th | Evening class: Project Presentation |
barnasaha.net 