Instructor: Barna Saha
Office: CS 322. Office phone: (413) 5772510. Email: barna@cs.umass.edu.
Office
Hours: Thur 11:30 am12:30 pm, CS322
Class
Time: TuTh 10:0011: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 NPhard. 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 nearoptimally. 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 34 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: 34 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
Midterm1
Solution. February 24^{th}.
Homework 3
Posted March 22^{nd},
Due April 9^{th} in the class. Homework 3 Solution
emailed. April 25^{th}
Midterm2
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 Homework1.
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:3012:30 pm on Tuesday, February 10^{th}.
4. MidtermI 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. Homework2 deadline extended to March 12^{th}. Office Hours: Mon, March 9^{th}
11:3012 noon, 1:302:00 pm.
7. We will have an implementation homework
(tentatively homework 4) to see how our LProunding methods work in practice.
8. No office hour on April 2^{nd}. We will have alternate
office hours on Friday, April 3^{rd} 1pm2pm.
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 kSubgraph Problem, U. Feige , G. Kortsarz , D. Peleg, Algorithmica 1999. Scribe: Ari Kobren (posted) 
Jan 22nd 
Greedy
Algorithms: Vertex Cover, Set Cover. 
Vazirani Book, Chapter 1, 2. Scribe: Sofya Vorotnikova (posted) 
Jan 27th 
Snow day:
class cancelled 

Jan 29th 
Local
Search: MAX Cut in undirected graphs: unweighted
and weighted 
Homework1 will
be posted over the weekend, and will be due in two weeks. Scribe:
David Tench (posted) 
Feb 3rd 
Submodular function optimization, local
search,. Dynamic programming: Knapsack 
Scribe: Conor Dowling (posted) U. Feige, V. Mirrokni and J. Vondrak.
Maximizing a nonmonotone 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) Vazirani Book, Chapter 8, 9 
Feb 10th 
Finish Bin Packing, Clustering Algorithms kcenter: 2approximation via parametric pruning kmedian local search 
Scribe: Sweetesh Singh Vazirani Book, Chapter 5 WilliamsonShmoys Book, Chapter 9.2 
Feb 12th 
Finish Local Search for kmedian.  David and Aditya
presented the remaining proof of Bin Packing from Feb 5^{th} class. 
Scribe:
Roman Lutz 
Feb 19th 
Simple Network Design Problems: Steiner Tree,
Traveling Salesman Problem, Multiway Cut 
Scribe: Aditya Sundarrajan Vazirani Book, Chapter 3 and 4. Homework1
due, Homework
2 posted. 
Feb 24th 
Midterm1 
Midterm1 Solution
Posted 
Feb 26th 
Warm up with Linear Program: Linear Program
Rounding for Vertex Cover/Set Cover Independent Randomized Rounding 
Scribe:
Stefan Dernbach Reading
Exercise: Vazirani Book, Chapter 12. 
Mar 3rd 
Scheduling, Unrelated Parallel Machines,
Basic Feasible Solution of LP 
Scribe: Luis
Pineda Vazirani Book, Chapter 17 
Mar 5th 
Iterative Relaxation, Unrelated Parallel
Machine Scheduling, Generalized Assignment Problems 
Scribe: Haoxi Zhan 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 12^{th}. Scribe: Matteo Brucato 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. 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 st 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, KMedian, Strengthening LP Relaxations 
Scribe: Liye Fu 
Apr 7th 
Randomized Rounding: Max k SAT,
PrizeCollecting Steiner Tree 
Scribe: Vijay Pemmaraju 
Apr 9th 
Prizecollecting Steiner Tree, Cuts and Metrics:
Multiway Cut 
Homework 3 due. Scribe: Garrett Bernstein 
Apr 14th 
Midterm2 

Apr 16th 
No Class due to instructor travel. 
Homework 4 posted on April 20^{th}
and due on May 4^{th}. 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 
Semidefinite programming Rounding, Max Cut 
Scribe:
Stefan Dernbach 