15-854 Approximation and Online Algorithms
MW 1:30-2:50. Wean 4615A. 12 Units
Course information and syllabus
Rough schedule and ideas for presentation topics
The final exam is now available. When you are ready to take it, click
Please feel free to send me email if you notice any mistakes.
- 01/19:Intro. Examples: Vertex
Cover, rent or buy, pursuer/evader.
Reading: section 2 of Shmoys. See also: Goemans intro, Rabani notes
- 01/24:Set-cover: greedy and
randomized rounding. p-center problem (symmetric and
Reading: [Panigrahy-Vishwanathan '98]. See also: Williamson lecture 2,
on set-cover, center & median problems.
- 01/26:Conditional expectation
method and randomized rounding: MAX-SAT and routing
problems. Related readings: Williamson lecture 5, Shmoys
section 3, Rabani notes.
- 01/31:Continuing with above. Also,
a little about approximation
hardness. Additional reading: Shmoys section 1, Goemans
- 02/02:A little more on approx
hardness, PTAS and FPTAS. More details on Clique hardness. Additional
reading: Williamson lecture 3.
- 02/07:The shortest
common superstring problem. We will be discussing work in BJLTY 1991. Latest
results in Sweedyk 1999/2000.
path song and lyrics.
- 02/09:The MAX-CUT problem and Semidefinite Programming.
Additional reading: Williamson lecture 6, Goemans section 5.
- 02/14:SDPs for approximate
3-coloring. Additional reading: Williamson lecture 7
(only proves the simpler version). Here is the KMS paper and the most recent bound.
- 02/16:Random projections and
approximate nearest neighbor.
- 02/21:Approximating metric spaces
with (heirarchical) tree metrics. Application to "buy at
bulk network design".
- 02/23:L_1 embeddings, Bourgain's
theorem, and balanced separators. Additional reading:
Cheriyan-Ravi Chapter 11.
and approximation hardness (Jochen Könemann). Here are
some more notes on the
- 03/01:On line algorithms: list update
and paging. Additional
reading: Goemans sections 1-4. Borodin and El-Yaniv Chapters
1 and 3.
- 03/08:Paging: deterministic and
randomized. Intro to k-server problem. Additional
reading: Borodin and El-Yaniv Ch 3,4.
- 03/13:Intro to k-server. The
Metrical Task System Problem (det and randomized).
Additional reading: Borodin and El-Yaniv Ch 9, 10.1-10.3
- 03/15:On-line machine
learning. Combining "expert" advice. Application to combining online
algorithms and proof of min-max. Here is a related survey paper.
- 03/20:On-line learning contd +
- 03/22:On-line search and
- 04/03:On-line load balancing and
virtual circuit routing. See
also Borodin and El-Yaniv Ch 12.1-12.3 and the survey
by Yossi Azar.
- 04/05:Decision theories and
metrics for online algorithms [Pat Riley and Elly Winner]
exact algorithms for 3-SAT and 2nd half [Ioannis Koutis and Ke Yang]
- 04/12:PTASs for dense instances of NP-hard problems. first half,
second half. [Amitabh
Sinha and Marcio Palmeira]
- 04/17:The Primal-Dual method
[Martin Zinkevich and Eric Bauer] See also Williamson's notes.
- 04/19:The k-server problem [Avrim
Blum]. See the latest paper by Koutsoupias.
- 04/24: Online learning
and the Winnow algorithm [Leejay Wu and Greg Schohn]
- 04/26: minimizing
OBDDs [Sanjit Seshia]
- 05/01: Online scheduling
[Nikhil Bansal and Bianca Schroeder]
- 05/03: Edge-dominating
sets [Ojas Parekh]. See also this
General wrap-up [Avrim Blum]
Handouts and Readings
Research papers and related lecture notes. David Williamson's notes
probably best tracks the material we will cover in the
approximation portion of the course.
Last modified: Sat May 13 19:03:28 EDT 2000