Advanced Algorithms 2008
Instructors: Uri Feige and Robi Krauthgamer
When and where: Thursdays 2-4pm, Ziskind 1
Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/AdvAlgs2008
Prerequisites: Basic knowledge in linear algebra and in algorithms.
Syllabus: Roughly speaking, the first half of the course will focus on Linear Programming, the second on algorithmic applications of it.
Assignments: Are due within 2 classes (typically 2 weeks)
Recommended reading (will be updated during the semester):
Lecture notes by Michel Goemans on Linear Programming.
Lecture notes by Uri Feige from Advanced Course on Algorithms 2004.
C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.
D. Bertsimas and J. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997.
J. Matousek and B. Gartner, Understanding and Using Linear Programming, Springer, 2006. (ebook)
Schedule: (weekly handout typically includes announcements, overview of topics covered, and problem sets)
|
Date |
Topic |
Reading |
Handout |
|
Feb. 14 |
Introduction to LP, geometry of LP |
Goemans' notes above, sections 1-5 |
|
|
Feb. 21 |
Basic feasible solutions, Simplex |
Goemans' notes above, sections 5-7 |
|
|
Feb. 28 |
Fourier-Motzkin elimination, remarks on Simplex, Beck-Fiala Theorem |
Feige's lecture notes |
|
|
Mar. 6 |
LP Duality |
Feige's lecture notes |
handout4 |
| Mar. 13 |
Basics of polyhedral theory | Goeman's notes on polyhedral
theory from combinatorial optimization course |
|
| Mar. 20 |
Ellipsoid algorithm |
Notes for lectures 6 and 7 |
handout6 |
| Mar. 27 |
--continued |
--same |
handout7 |
| Apr. 3 |
Relaxation, integrality gap,
total unimodularity, half-integrality |
Feige's notes (lecture 9) |
handout8 |
| Apr. 10 |
Perfect graphs and the Lovasz
theta function |
Feige's lecture notes |
handout9 |
| Apr. 17 |
Multiplicative Weights method
and solving LPs approximately |
Survey
paper by Arora, Hazan and Kale |
handout10 |
| Apr. 24 |
no class (passover) |
||
| May 1 |
Randomized rounding of LPs |
Vazirani's book Sections 14, 16 |
handout11 |
| May 8 |
no class (independence day) |
||
| May 15 |
no class (cancelled) |
||
| May 22 |
Max-Cut in planar graphs and
coloring 3-colorable graphs |
Notes for lecture 12 |
n/a |
| May 29 |
Computing a coloring in a
perfect graph and Summary (change in time to 11am) |
Feige's lecture notes | summary |
| June 12 |
EXAM |
exam |
Announcements:
Problem set 5: In question 2, assume P is bounded (i.e. a polytope)
Problem set 8: In question 3, change "every integral solution" into
"every optimal-integral solution", and assume the weights are
(strictly) positive.
Exam: The exam is scheduled to June 12 (same time and place as the
class).
Problem set 11: This problem set is *mandatory*
(i.e. CHOVAT HAGASHA), unlike the other problem sets, and in fact will
be given higher weight in the final grade.
The last class on May 29 will take place at 11am.