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

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 1st , Due February 19th  in the class. Homework 1 Solution

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

Midterm-1 Solution. February 24th.

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

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

Homework 4 Emailed April 20th,  Due May 4th
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.


      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 12th. Instead, I will hold office hours 11:30-12:30 pm on Tuesday, February 10th.

4.    Midterm-I on February 24th.

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 12th.  Office Hours: Mon, March 9th 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 2nd. We will have alternate office hours on Friday, April 3rd  1pm-2pm.

9.    Final exam will be take home. It will be posted on April 28th at 5pm and will be due on April 29th 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





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 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.




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


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


Apr 9th

Prize-collecting Steiner Tree, Cuts and Metrics: Multiway Cut

Homework 3 due.

Scribe: Garrett Bernstein

Apr 14th


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


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


Scribe: Stefan Dernbach