Advanced Algorithms 2008
Instructors: Uri Feige and Robi Krauthgamer
When and where: Thursdays 24pm, 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, PrenticeHall, 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 15 

Feb. 21 
Basic feasible solutions, Simplex 
Goemans' notes above, sections 57 

Feb. 28 
FourierMotzkin elimination, remarks on Simplex, BeckFiala 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, halfintegrality 
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 
MaxCut in planar graphs and
coloring 3colorable 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 optimalintegral 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.