·
The Design of
Approximation Algorithms by David Williamson and David Shmoys,
Cambridge University Press, 2011 (main).
* Online (but
non-printable) version is available:
http://www.designofapproxalgs.com/download.php
·
Approximation
Algorithms by Vijay Vazirani, Springer-Verlag, 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 Har-Peled, UIUC.
·
Combinatorial Optimization, Spring
2010 by Chandra Chekuri, UIUC.
Approximation algorithm design
techniques: Greedy approach, dynamic
programming, randomization, local search, linear programming and rounding,
semi-definite 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:
k-center, k-median, k-means, 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 well-known inapproximability
results and approximation-preserving 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 NP-hard - 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. |
HW1-A released (deadline 9/11) |
9/9 |
Knapsack. PTAS/FPTAS. - Section
1 in 2011 CC Lecture 6. - Chapter 3 in WS. - Chapter 8 in V. |
HW1-B 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. |
HW2-A 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 |
k-Center - Chapter 5 in V. - Chapter 2.2 in WS. Multiway cut,
k-cut - Chapter 4 in V. - Chapter 8 in WS. |
HW2-B released (deadline
10/2) |
9/25 |
Multiway cut,
k-cut (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. |
HW3-A 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’) |
HW3-B 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. |
HW4-A released (deadline
10/23) |
10/16 |
Scheduling Problems and Separation Oracle. - Chapter 4.1-4.3
in WS. |
|
10/21 |
Scheduling Problems and Separation Oracle. (Cont’) Introduction to Local Search: Weighted Max Cut |
|
10/23 |
Local Search: k-Median - 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 k-Median. |
HW4-B released (deadline 10/30) |
10/28 |
Min-cost 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 Primal-Dual
Approach to Online Optimization Problems by Seffi Naor - Survey on Multiplicative
weights update method by Arora, Hazan
and Kale |
|
12/4 |
(Cont’) |
Final
(take-home) 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 NP-hard, or
APX-hard?
- 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 Non-Monotone 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
Non-monotone 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 Flow-time explained by Dual Fitting S. Anand, N. Garg, A. Kumar. SODA 2012
§ SelfishMigrate:
A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous
Processors J. Kulkarni, S. Im, K. Munagala and K. Pruhs. FOCS
2014
§ Online Primal-Dual for
Non-linear 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 meta-algorithm 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.