Home Page for CMPSCI 690AA (Approximation Algorithms & Combinatorial Optimization)

Instructor: Barna Saha Office: CS 322. Office phone: (413) 577-2510. E-mail: barna@cs.umass.edu.

Office Hours: Thur 11:30 am--12:30 pm, CS322

Class Time: TuTh 10:00--11:15am. LGRC A310.

Class Discussion Blog: cmpsci690aa.wordpress.com  

Lecture Notes will be posted on the Course Blog

Course Overview: Many important problems that arise in practical applications of discrete optimization are NP-hard. This implies no polynomial time algorithms exist for these problems unless P==NP. The field of approximation algorithms has developed to tackle this difficulty by designing polynomial time algorithms to solve otherwise intractable problems near-optimally. Approximation algorithms provide rigorous guarantees on approximation factors indicating how far the solution can be in the worst case. This paradigm has become a cornerstone in algorithm design, and this course aims to cover a comprehensive list of topics in this area at the graduate level. Towards the end of the course, we will also explore ``hardness of approximation'': study of the best approximation factor possible in polynomial time.
A tentative list of topics include

• Techniques: Greedy algorithms, local search, dynamic programming, randomized methods, LP techniques, primal-dual method, lagrangian methods, semi-definite programming, metric method, hardness of approximation.
• Problems: Set cover, Vertex cover, TSP and other planning problems, Scheduling and Generalized assignment problems, Facility Location, Steiner tree and other network design problems, Sparsest cut, multicut and other graph partitioning problems, MaxSat, Graph coloring, Approximate counting, Algorithms on sequences etc.

Text Books
Our main text books will be the following two books, but we will also include several recent papers in our discussion.

Vijay Vazirani, Approximation Algorithms, Springer, 2001.
David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.

Prerequisities The main prerequisites for this class are mathematical maturity, exposure to algorithm design and analysis at the advanced undergraduate or beginning graduate level (CMPSCI 611, or CMPSCI 311 with instructor permission) and a solid grounding in linear algebra and probability theory. Students without such background can seek permission of the instructor.

Requirements and Grading There will be 3-4 homeworks, two midterms and an endterm, all in class and closed book. Homework assignments will count for 20% of the grade, the best of two midterms will count 30%, and the final exam will count for 30%. 10% of the grade will be allocated to blog/class participation, and 10% for writing scribe. Homeworks need to be done in a group of two. No collaboration outside the group is allowed. No collaboration is allowed in the exams.

Homeworks:  3-4 homeworks and practice problems will be given.

Homework 1  Posted February 1^st , Due February 19^th  in the class. Homework 1 Solution

Homework 2 Posted February 19^th,  Due March 12^th in the class. Homework 2 Solution

Midterm-1 Solution. February 24^th.

Homework 3 Posted March 22^nd,  Due April 9^th in the class. Homework 3 Solution emailed. April 25^th

Midterm-2 Solution. Midterm 2 Solution emailed. April 25^th

Homework 4 Emailed April 20^th,  Due May 4^th
     
Late Homework Policy: Students will be allowed a maximum of 2 late days for homework to be used in integer amounts and distributed as the student sees fit. No additional late days are allowed.

Acknowledgement: I would like to thank Chandra Chekuri and Anupam Gupta for making their course content on Approximation Algorithms available online. Those have helped me to plan this course better.

Announcements

      0.   Lecture notes are available from the course blog.

1.     Please check the corrected Homework-1.

2.    Lecture notes are due within 2 days of the lecture. You need to ask for special permission if you cannot meet the timeline.  There will be a 50% deduction of points if lecture notes are submitted after 2 days of class without permission. Lecture notes submitted after a week of the class will not get any credit.

3.    There will be no office hours on Thursday, February 12^th. Instead, I will hold office hours 11:30-12:30 pm on Tuesday, February 10^th.

4.    Midterm-I on February 24^th.

5.    There will be additional lectures on Metric Embedding as part of Big Data Algorithms Class. Please try to attend.

6.    Homework-2 deadline extended to March 12^th.  Office Hours: Mon, March 9^th 11:30-12 noon, 1:30-2:00 pm.

7.    We will have an implementation homework (tentatively homework 4) to see how our LP-rounding methods work in practice.

8.    No office hour on April 2^nd. We will have alternate office hours on Friday, April 3^rd  1pm-2pm.

9.    Final exam will be take home. It will be posted on April 28^th at 5pm and will be due on April 29^th at noon. No collaboration is allowed in the final exam. However it is allowed to consult the lecture notes and the two text books.

 

Class Schedule

 

Lecture	Topic	References/Announcements
Jan 20th	Class logistics, why study approximation algorithms?--motivating example: approximate dense subgraph computation	Greedy Approximation Algorithms for Finding Dense Components in a Graph, M. Charikar, APPROX, 2000 On Finding Dense Subgraph, S. Khuller, B. Saha,  ICALP, 2009 The Dense k-Subgraph Problem, U. Feige , G. Kortsarz , D. Peleg, Algorithmica 1999. Blog Link Scribe: Ari Kobren (posted)
Jan 22nd	Greedy Algorithms: Vertex Cover, Set Cover.	Vazirani Book, Chapter 1, 2. Blog Link Scribe: Sofya Vorotnikova (posted)
Jan 27th	Snow day: class cancelled
Jan 29th	Local Search: MAX Cut in undirected graphs: unweighted and weighted	Homework-1 will be posted over the weekend, and will be due in two weeks. Blog Link Lecture note from MIT Scribe: David Tench (posted)
Feb 3rd	Submodular function optimization, local search,. Dynamic programming: Knapsack	Scribe: Conor Dowling (posted) Blog Link U. Feige, V. Mirrokni and J. Vondrak. Maximizing a non-monotone submodular function. FOCS, 2007. Vazirani Book, Chapter 8. Lecture note from Stanford: greedy algorithm for maximizing monotone submodular function subject to additional constraints
Feb 5th	FPTAS , PTAS: Knapsack, Bin packing	Scribe: Ian Gemp (posted) Blog Link   Vazirani Book, Chapter 8, 9
Feb 10th	Finish Bin Packing, Clustering Algorithms k-center: 2-approximation via parametric pruning k-median local search	Scribe: Sweetesh Singh Blog Link   Vazirani Book, Chapter 5 Williamson-Shmoys Book, Chapter 9.2
Feb 12th	Finish Local Search for k-median. --------- David and Aditya presented the remaining proof of Bin Packing from Feb 5th class.	Blog Link Scribe: Roman Lutz
Feb 19th	Simple Network Design Problems: Steiner Tree, Traveling Salesman Problem, Multiway Cut	Scribe: Aditya Sundarrajan   Blog Link   Vazirani Book, Chapter 3 and 4.   Homework-1 due, Homework 2 posted.
Feb 24th	Midterm-1	Midterm-1 Solution Posted
Feb 26th	Warm up with Linear Program: Linear Program Rounding for Vertex Cover/Set Cover   Independent Randomized Rounding	Scribe: Stefan Dernbach   Blog Link   Reading Exercise: Vazirani Book, Chapter 12.
Mar 3rd	Scheduling, Unrelated Parallel Machines, Basic Feasible Solution of LP	Scribe: Luis Pineda   Blog Link   Vazirani Book, Chapter 17
Mar 5th	Iterative Relaxation, Unrelated Parallel Machine Scheduling, Generalized Assignment Problems	Scribe: Haoxi Zhan   Blog Link   Chapter 11, Shmoys and Williamson
Mar 10th	Iterative Relaxation Continued.   Integrality of Matching Polytope Bounded Degree Spanning Tree Problem, Integrality of Spanning Tree Polytope	Homework 2 deadline extended to March 12th. Scribe:  Matteo Brucato   Blog Link   Chapter 11, Shmoys and Williamson
Mar 12th	Contd. Bounded Degree Spanning Tree Problem,   LP Duality, Primal Dual Algorithms   Reading Exercise. Dual Fitting for set cover. (Chapter 13, Vazirani Book)	Scribe: Matteo Brucato   Homework 3 will be posted over the weekend.   Slides   Blog Link   Chapter 11, Shmoys and Williamson Chapter A, Shmoys and Williamson Chapter 15, Vazirani Book
Mar 24th	Primal Dual Algorithms: Set Cover, Feedback Vertex Set, Shortest s-t Path	Scribe: Kevin Winner Chapter 7,  Shmoys and Williamson
Mar 26th	Primal Dual Algorithm for Generalized Steiner Tree (Steiner Forest) problem	Scribe: Xiaolan Wang Slides
Mar 31st	Primal Dual for Uncapacitated Facility Location	Scribe: Xiaolan Wang
Apr 2nd	Lagrangian Relaxation, K-Median, Strengthening LP Relaxations	Scribe: Liye Fu
Apr 7th	Randomized Rounding: Max k SAT, Prize-Collecting Steiner Tree	Scribe: Vijay Pemmaraju Slides
Apr 9th	Prize-collecting Steiner Tree, Cuts and Metrics: Multiway Cut	Homework 3 due. Scribe: Garrett Bernstein
Apr 14th	Midterm-2
Apr 16th	No Class due to instructor travel.	Homework 4 posted on April 20th and due on May 4th. Please carefully check the assignment of problems to groups in Homework 4.
Apr 21st	Multiway Cut Contd. Probabilistic Approximation of Metrics by Tree Metric	Slides Scribe: Ari Kobren
Apr 23rd	Probabilistic Approximation of Metrics by Tree Metric, Further use of Randomization in Approximation Algorithms.	Scribe: David Tench
Apr 28th	Semi-definite programming Rounding, Max Cut	Slides Scribe: Stefan Dernbach