New Directions in Approximation Algorithms

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.

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.

Notes: See J. Vondrak’s tutorial.

Notes on submodular function maximization.

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.

Lovasz extension and connection to Edmond’s greedy algorithm
(also many nice examples of submodular functions in practice)
Sept 23Deterministic 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 ProblemChapter 7 of Williamson-Shmoys
Oct 7-21Cuts & Metrics
Multiway Cut
Probabilistic Embedding on Tree Metric with Applications
Chapter 8 of Williamson-Shmoys
Notes on Ellipsoid algorithm
Oct 28Semi-definite programming rounding. MAX CUT, MAX-2SATChapter 6 of Williamson-Shmoys
Nov 4 Local RatioGuest Lecturer: Seri Khoury
Maximum Independent Set via local ratio
Nov 6Evening Presentation:
Dependent Rounding

Semi-definitie programming rounding for MAX-SAT

More on Submodular Maximization
Dependent Rounding and Its Applications to Approximation Algorithms  

A 7/8-Approximation Algorithm for MAX 3SAT

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
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:
[ETH, SETH, Reduction of k-SAT to OV]
Proof of the Sparsification lemma
Nov 13 Evening Presentation
Computing Edit Distance Fast
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time

Constant-factor approximation of near-linear edit distance in near-linear time
Nov 18 OV to Sequence Alignment Problems: Edit Distance.   References:
Nov 18 Presentation:
Faster Approximation of the Longest Common Subsequence Problem.

Computing CFG parsing fast.

Reducing approximate Longest Common Subsequence to approximate Edit Distance

General context-free recognition in less than cubic time
Nov 20Distributed 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  
Nov 27Fast Algorithm for APSP in non-uniform model.References:  
Dec 2nd Fast Approximation Algorithms for APSP.   References:  
Dec 4th Fast Exact Algorithm for (min,+) matrix multiplication on Lipschitz matrices.   References:  
Extra Topics Dynamic Problems & Hardness   Reference:  
Extra TopicsDynamic Algorithms: design of dynamic algorithms via primal-dualReference:
Dec 4thEvening class:
Project Presentation