· 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 |
|
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. |
|
|
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. See NP, P, NPC. Weakly/strongly NP-hard - lecture
notes by Jeff Erickson Lecture
note by Chandra Chekuri on Minimum Spanning
Tree |
|
|
Greedy
Algorithms. Set Cover & Max Coverage - Section
1 in 2011 CC Lecture 1. -
Section 1.6 in WS. -
Section 3.1 in V. |
|
|
Knapsack. PTAS/FPTAS. - Section
1 in 2011 CC Lecture 6. - Chapter 3 in WS. - Chapter 8 in V. |
|
|
Makespan on
Identical Machines - Section
1 in 2009 CC Lecture 5. - Chapter 10 in V. - Chapter 3 in WS. |
|
|
Bin Packing - Section
1 in 2009 CC Lecture 5. - Chapter 9 in V. - Chapter 3.3 in WS. |
|
|
k-Center - Chapter 5 in V. - Chapter 2.2 in WS. |
|
|
Scheduling jobs with precedence constraints on identical
machines. Discussion on hw2A |
|
|
|
Multiway cut, k-cut * See Jeff
Erickson’s lecture note and Chandra Chekuri’s
slides (1, 2, 3, 4)
for max flow and min cut |
|
Introduction to LP
and its applications to approximation algorithms - Appendix A in WS. - Chapter 1.3 in WS. - Chapter 12 in V. |
|
|
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. |
|
|
Randomized Rounding, Chernoff
Bounds - Chapter 5.10, 5.11 in WS. |
|
|
|
Facility Location - 2005
Anupam Gupta’s lecture note (10/31) - Chapter 4.5 in
WS. |
|
Scheduling Problems and Separation Oracle. - Chapter 4.1-4.3
in WS. |
|
|
Introduction to Local Search: Weighted Max Cut http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec07.pdf |
|
|
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. (Only the above topics will be tested in Final
Exam) |
|
|
Min-cost bipartite matching, Min makespan
on unrelated machines, Generalized Assignment Problem (GAP). - Gupta
and Ravi’s lecture note. - Chapter 11.1 in
WS. |
|
|
Group Steiner Tree. |
|
|
Multicut |
|
|
Sparsest Cut Tree and L_1 Embeddings |
|
|
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/15 |
Final
Exam (3:00-6:00pm) in SSM 100 |
|
12/16 |
Project
Deadline (11:59pm) |
·
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.