[Course description] [Announcements] [Lectures] [Assignments] [Reading material]

**Instructors:** Uriel Feige
and Robert
Krauthgamer

**When and where:** Thursday 2-5pm, FGS room C

**FGS code:** 20124151.

**Syllabus:** The course will cover theoretical design and
analysis of algorithms, focusing on computational problems
involving combinatorial optimization, such as cuts, flows and
distances in graphs. The emphasis will be on modern algorithmic
approaches for finding either exact or approximate (near-optimal)
solutions, using tools such as mathematical programming, matrix
analysis, geometry, sparsification and compression.

**Prerequisites:** Students are expected to be familiar with
algorithms, complexity theory, probability theory, and linear
algebra, at an undergraduate level.

**Webpage:**
http://www.wisdom.weizmann.ac.il/~robi/teaching/2012a-AdvancedAlgorithms

- posted 2012-02-16: graded homework (#5 and #6) can be picked
up from Sharon/Carol's office (Ziskind room 228).

- posted 2012-01-12: added clarification to problem set 4
question 2.

- posted 2011-12-31: The exam
was (re)scheduled to Feb. 23, 2012 at 10am (FGS room C).

- Nov. 3, Uri: The basics of Linear Programming [lecture notes #1]
- Nov. 10, Uri: The simplex and ellipsoid algorithms [supplementary reading: lecture notes on simplex and on ellipsoid]
- Nov. 17, Uri: Duality and total unimodularity [lecture notes #3]

- Nov. 24, Robi: Flow/cut gaps (single-commodity and multi-commodity) [lecture notes #4]
- additional reading: lecture notes by Trevisan, book by Vazirani
- Dec. 1, Robi: Concurrent-flow/sparsest-cut gap [lecture notes #5]
- additional reading: lecture notes by Rao-Vazirani, book by
Vazirani

- Dec. 8, Robi: Spectral graph theory (basics and easy direction of Cheeger's inequality) [lecture notes #6]
- additional reading: lecture notes by Spielman and by
Trevisan, book by Chung.

- Dec. 15, Robi: Cheeger's inequality (cont'd) and balanced-cut [lecture notes #7]
- additional reading: same as last week

- Dec. 22, Robi: Prediction using experts, Multiplicative
Weights, and application to fast approximate LP solver [lecture notes #8]

- additional reading: survey by Arora-Hazan-Kale,
lecture notes by Rao-Vazirani and by Gupta

- Dec. 29, Uri: Treewidth and graph minors
- Jan. 5, Uri: Treewidth and graph minors (cont'd) [lecture notes #9+10]

- Jan. 12, Uri: Vertex separators and low treewidth k-coloring

- Jan. 19, Uri: Vertex separators and low treewidth k-coloring (cont'd) [lecture notes #11+12]
- Jan. 26, Robi: Graph compression and cut sparsifiers [lecture notes #13]

- Feb. 2, Robi: Graph sparsification for distances [lecture notes #14]

- handout1 (from Nov. 3)
- handout2 (from Nov. 17,
duality)

- problem set 3 (posted Dec. 2, flow/cut gaps)
- problem set 4 (posted Dec. 23, spectral graph theory + prediction using experts)
- clarification for question #2: Assume G has unit edge-weights, and that the balance (1/2 or 2/3) is measured with respect to vertex-weights (where weight=degree).
- handout5 (posted Jan. 5)
- handout6 (from Jan. 19)
- problem set 7 (posted Feb. 4, extra
credit only)

- Linear Programming by Karloff
- Understanding and Using Linear Programming by Matoušek and Gärtner
- Approximation Algorithms by Vazirani
- The Design of Approximation Algorithms by Williamson and Shmoys
- Spectral
Graph Theory by Fan Chung

- Advanced algorithms by Feige and Krauthgamer at Weizmann (2008) [related but not identical]
- Combinatorial Algorithms and Data Structures by Satish Rao and Umesh Vazirani (2011)
- Graph Partitioning and Expanders by Luca Trevisan (2011)
- Optimization
and Algorithmic Paradigms by Luca Trevisan (2011)

- Spectral
Graph Theory by Dan Spielman (2009)

- Advanced Algorithms by Michel Goemans at MIT (2008)
- Advanced Algorithms by Shuchi Chawla at U. Wisconsin (2007)
- Advanced Algorithms by Jon Kleinberg at Cornell (2001)