New Directions in Approximation Algorithms

Under Construction.

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 solution. 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 present one/two papers and do a research project individually or in a group of two. Class presentations account for 30% of the grade and the project accounts for 70%. Project will have several components: (i) project proposal (less than 1 pg) due on Sept 18, (ii) intermediate progress report (less than 2 pgs) due on Oct 23, (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.

Date            Topic Notes
Aug 28 Overview of the course.
The whats and whys of approximation algorithms.
Brief introduction to linear programming and LP duality.
Chapter 1 of Williamson-Shmoys, Chapter 12 of Vazirani.  
Sept 4 An introduction to the techniques through the set cover problem:
deterministic rounding, primal-dual, randomized rounding.
Chapter 1 of Williamson-Shmoys.  
Sept 9 An introduction to the techniques through the set cover problem:
greedy algorithm, dual fitting.  
Chapter 1 of Williamson-Shmoys, Chapter 13 of Vazirani.  
Sept 11 The uncapacitated facility location problem: randomized rounding.Chapter 5.8 of Williamson-Shmoys.  
Sept 16 The uncapacitated facility location: primal-dual method.   Chapter 7.6 of Williamson-Shmoys  
Sept 18 Introduction to semi-definite programming. Randomized rounding of semi-definite programming.   Chapter 6 of Williamson-Shmoys  
Sept 23 Student presentation on choice papers under traditional approximation algorithms  
Sept 25 Student presentation on choice papers under traditional approximation algorithms    
Sept 30 Techniques in proving hardness of approximation: a brief introduction.   Chapter 10 of Williamson-Shmoys.  
Oct 2 A fine-grained approach to hardness: ETH, SETH, OV. SETH to OV, OV to 2-3 Diameter.   Reference: https://people.csail.mit.edu/virgi/6.s078/  
Oct 7 A fine-grained approach to hardness: More on SETH and ETH.Reference: https://people.csail.mit.edu/virgi/6.s078/  
Oct 9 OV to Sequence Alignment Problems: Longest Common Subsequence, Edit Distance.   References: https://arxiv.org/abs/1412.0348
https://arxiv.org/abs/1501.07053
Oct 14 Amnesic Dynamic Programming: Longest Increasing Subsequence
& RNA Folding.
References:
http://ieee-focs.org/FOCS-2017-Papers/3464a295.pdf
https://arxiv.org/abs/1308.0626
Oct 16 ——–Buffer ———    
Oct 21 Instructor travel, no class    
Oct 23 Edit Distance Approximation References:
https://arxiv.org/abs/1810.03664
Oct 28
APSP, (min,+) matrix multiplication and Equivalences  
References: https://people.csail.mit.edu/rrw/tria-mmult.pdf  
Oct 30 Fast Algorithm for APSP in non-uniform model.References:
https://people.csail.mit.edu/virgi/6.s078/lec12-LDTs.txt  
Nov 4 Fast Approximation Algorithms for APSP.   References:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.4076&rep=rep1&type=pdf  
Nov 6 Fast Exact Algorithm for (min,+) matrix multiplication on Lipschitz matrices.   References:
https://arxiv.org/abs/1707.05095  
Nov 13 Student Presentation of choice papers under fine-grained complexity    
Nov 18 Student Presentation of choice papers under fine-grained complexity    
Nov 20 Dynamic Problems & Hardness   Reference:
https://people.csail.mit.edu/virgi/6.s078/lec14-dynamic.pdf  
Nov 25 Dynamic Algorithms: design of dynamic algorithms via primal-dualReference:
https://arxiv.org/abs/1604.05337
 
Dec 2 Project Presentation    
Dec 4 Project Presentation