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):

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

handout1

Feb. 21

Basic feasible solutions, Simplex

Goemans' notes above, sections 5-7

handout2

Feb. 28

Fourier-Motzkin elimination, remarks on Simplex, Beck-Fiala Theorem

Feige's lecture notes

handout3

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

handout5

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.