·
The Design of
Approximation Algorithms by David Williamson and David Shmoys,
Cambridge University Press, 2011 (main).
* Online (but
nonprintable) version is available:
http://www.designofapproxalgs.com/download.php
·
Approximation
Algorithms by Vijay Vazirani, SpringerVerlag, 2004.
·
Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
·
Combinatorial Optimization by Schrijver
·
Introduction to Algorithms by Cormen,
Leiserson, Rivest, and
Stein.
·
Algorithm Design, Kleinberg and Tardos
·
Approximation Algorithms, Fall 2013, Spring 2011, Spring 2009 by
Chandra Chekuri, UIUC.
·
Approximation Algorithms, Fall 2005
by Anupam Gupta and R. Ravi, CMU.
·
Algorithms
lecture notes, old homeworks and exams by Jeff
Erickson, UIUC.
·
Lecture
notes and problems on algorithms by Sariel HarPeled, UIUC.
·
Combinatorial Optimization, Spring
2010 by Chandra Chekuri, UIUC.
Approximation algorithm design
techniques: Greedy approach, dynamic
programming, randomization, local search, linear programming and rounding,
semidefinite programming and rounding, and metric embedding.
·
Covering
problems: vertex cover, knapsack cover, and set cover
·
Scheduling
problems: single/multiple machine scheduling, precedence constraints, and
generalized assignment
·
Packing problems:
bin packing, knapsack, max coverage, and max independent set
·
Submodular optimization and its applications
·
Clustering:
kcenter, kmedian, kmeans, and facility location
·
Tour problems:
metric TSP, asymmetric TSP, and orienteering
·
Network design
problems: Steiner trees/forests, and survival network design
·
Cut problems: max
cut, multiway cut, multicut,
sparsest cut
·
Routing problems:
multicommodity flow, congestion minimization, unsplittable flow
Intro to inapproximability: several wellknown inapproximability
results and approximationpreserving reduction
Date 
Topics 
Homework
and etc. 
8/28 
Administrivia and Course
Introduction Course Intro:  Section
1 in 2011 CC Lecture 1.  Chapter 1.1 in WS. Decision version of NP vs Optimization
version of NP (NPO).  Section
2.1 in 2011 CC Lecture 2.  NP, P, NPC. 
HW0 released. HW0 will not be
graded. 
9/2 
Course Intro (cont’) and Traveling
Salesman Problem (TSP)  Section
1 in 2011 CC Lecture 2. 
Chapter 2.4 in WS.  Chapter 3.2 in V; tight examples
are shown. NP, P, NPC. Weakly/strongly NPhard  lecture
notes by Jeff Erickson 

9/4 
Greedy Algorithms. Set Cover, Max Coverage, Steiner Tree.  Section
1 in 2011 CC Lecture 1. 
Section 1.6 in WS. 
Section 3.1 in V. 
HW1A released (deadline 9/11) 
9/9 
Knapsack. PTAS/FPTAS.  Section
1 in 2011 CC Lecture 6.  Chapter 3 in WS.  Chapter 8 in V. 
HW1B released (deadline
9/18) 
9/11 
Makespan on
Identical Machines  Section
1 in 2009 CC Lecture 5.  Chapter 10 in V.  Chapter 3 in WS. 

9/16 
Bin Packing  Section
1 in 2009 CC Lecture 5.  Chapter 9 in V.  Chapter 3.3 in WS. Scheduling jobs with precedence constraints on identical
machines. 
HW2A released
(deadline 9/25) (Last Updated 10/1: there was a small bug in Problem 1,
and it was fixed). 
9/18 
Wrapping up things: Knapsack, Makespan,
Bin Packing… 
Last Day to Add/Drop Courses 
9/23 
kCenter  Chapter 5 in V.  Chapter 2.2 in WS. Multiway cut,
kcut  Chapter 4 in V.  Chapter 8 in WS. 
HW2B released (deadline
10/2) 
9/25 
Multiway cut,
kcut (cont’) * See Jeff
Erickson’s lecture note for max flow and min cut 

9/30 
Introduction to LP and its applications to approximation
algorithms  Appendix A
in WS.  Chapter 1.3 in WS.  Chapter 12 in V. 
HW3A released (deadline
10/9) 
10/2 
LP primal and dual: max flow and min cut, revisiting Set
Cover.  Chapter 12 in V.
 Chapter 1 in WS.  Chapter 13, 14, 15 in V. 

10/7 
(cont’) 
HW3B released (deadline
10/16) 
10/9 
Randomized Rounding, Chernoff
Bounds  Chapter 5.10, 5.11 in WS. 

10/14 
Facility Location  2005
Anupam Gupta’s lecture note (10/31)  Chapter 4.5 in WS. 
HW4A released (deadline
10/23) 
10/16 
Scheduling Problems and Separation Oracle.  Chapter 4.14.3
in WS. 

10/21 
Scheduling Problems and Separation Oracle. (Cont’) Introduction to Local Search: Weighted Max Cut 

10/23 
Local Search: kMedian  Section 2 in
Lecture 6 of Anupam Gupta’s 2008 Advanced Approx. Algorithms.  Gupta and Tangwonsan’s
analysis of local search for Facility Location and kMedian. 
HW4B released (deadline 10/30) 
10/28 
Mincost bipartite matching, Min makespan
on unrelated machines, Generalized Assignment Problem (GAP).  Gupta
and Ravi’s lecture note.  Chapter 11.1 in
WS. 

10/30 
Group Steiner Tree. 

11/4 
Group Steiner Tree (cont’) 

11/6 
Multicut 


No lecture due to Veterans Day Holiday 

11/13 
Sparsest Cut 


No lecture due to instructor’s travel 


No lecture due to instructor’s travel 

11/25 
Tree and L_1 Embeddings 


No lecture due to Thanksgiving Holiday 

12/2 
Online Algorithms  Lecture notes by
Serge Plotkin  Who
solved the Secretary Problem by T. Ferguson  A PrimalDual
Approach to Online Optimization Problems by Seffi Naor  Survey on Multiplicative
weights update method by Arora, Hazan
and Kale 

12/4 
(Cont’) 
Final
(takehome) exam released at 06:35pm. See
UCMCROPS (resources). 
12/12 
Project report and final exam due at 11:59pm (PST) 

12/19 

Fall semester ends 
12/22 

Final grades due 
·
The ideal project would be the following.
 Find a problem in your area. Motivation and introduction are
expected.
 Formalize the problem. You will need to decide what aspects
to keep or discard. Balance is important: too many details will obscure
algorithmic ideas and too few details will make the problem less realistic.
 Find connection to known problems. For some special cases,
your problem may be already known. Summarize the previous work.
 Discuss the complexity of the problem. Is it NPhard, or
APXhard?
 Give approximation algorithms if needed. This course is on
approximation algorithms, so you are strongly encouraged to apply what you
learned to your problem.
 Try various methods: greedy, dynamic programming, linear
programming and rounding, etc. Explain why they work or not. If you don’t know
how to analyze, simply state that. If the general case is hard, you can try
some special cases.
 Do some simple experiments if needed.
·
You are required to write a final report. I can hardly imagine a report of less than 5 pages
that includes the intro, problem definition, attempted approaches, etc. But
there exist really wonderful papers that are very short, so the length is not
everything.
·
If you still haven’t chosen a project and have no idea, you
can write a survey paper. For example,

Unconstrained NonMonotone Submodular Function
Maximization
§ A
Tight Linear Time (1/2)Approximation for Unconstrained Submodular
Maximization N. Buchbinder,
M. Feldman, J. Naor, R. Schwartz. FOCS 2012
§ Maximizing
Nonmonotone Submodular Functions U.
Fiege, M. Feldman, V. Mirronkni,
J. Vondrak. FOCS 2012
 Potential Functions for Online
Scheduling
§ A Tutorial
on Amortized Local Competitiveness in Online Scheduling S. Im, B. Moseley, K. Pruhs. ACM SIGACT
News (June 2011)
§ Scalably
scheduling processes with arbitrary speedup curves J. Edmonds, K. Pruhs, SODA 2009
 Dual
Fitting For Online Scheduling
§ Resource Augmentation
for Weighted Flowtime explained by Dual Fitting S. Anand, N. Garg, A. Kumar. SODA 2012
§ SelfishMigrate:
A Scalable Algorithm for Nonclairvoyantly Scheduling Heterogeneous
Processors J. Kulkarni, S. Im, K. Munagala and K. Pruhs. FOCS
2014
§ Online PrimalDual for
Nonlinear Optimization with Applications to Speed Scaling A. Gupta, R. Krishnaswamy, K. Pruhs. WAOA
2012
 Dependent Randomized
Rounding and Applications
§ Pipage Rounding: A New Method of Constructing Algorithms
with Proven Performance Guarantee. A. Ageev and
M. Sviridenko.
J. of Combinatorial Optimization 2004; preliminary version appeared
as "Approximation algorithms for Maximum Coverage and Max Cut with given
sizes of parts" in IPCO 1999.
§ Dependent Rounding
and its Applications to Approximation Algorithms. R. Gandhi, S. Khuller, S. Parthasarathy, A.
Srinivasan. J. of the ACM, 2006.
 Solving Packing and
Covering LPs Approximately
§ Randomized
Rounding Without Solving the Linear Program. N. Young. SODA 1995.
§ Faster
and Simpler Algorithms for Multicommodity Flow and
other Fractional Packing Problems.. N. Garg and J. Konemann. SIAM
J. on Computing, 2007; preliminary
version in FOCS 1998.
§ Multiplicative
weights method: a metaalgorithm and its applications. S. Arora, E. Hazan, S. Kale.
§ Fast approximation
algorithms for fractional packing and covering problem. S. Plotkin, D. Shmoys, E. Tardos. Math. of
Operations Research, 1995; preliminary version in FOCS 1991.
·
You are strongly
encouraged to type in their solutions in latex.
·
Solutions should be concise.
Highlighting key ideas will be useful.
Your goal is to convince me that you
know the solutions.
·
You can discuss homeworks with
others in groups
of size up to 3. Each of you must submit your own solutions, and clearly note
at the beginning of the first page the names of students you collaborated with.
·
One should not possess of a copy of all or part of the work
done by someone else, in the form of an email, an email attachment file, a
storage device, or a hard copy.
·
You can change their groups for each
homework.
·
You can use materials found on the web or in books or papers.
However, you must write the solutions in your own words and cite the sources
clearly.
·
There should be no student left alone unless the student wants
to do so. If students do not follow this rule, the instructor has the right to
change groups.
·
Deadline extension will be allowed up to one week only for
the following reasons: illness or travel for academic reasons. You need to
provide the proof such as a letter from doctor. Other reasons need to be
approved by the instructor.
·
If you cheat on a homework, you will
get zero point for the homework. If you cheat again, you will fail the course.