Jan 16 |
Introduction to approximation algorithms. Introduction to the techniques: Set cover. LP rounding, dual rounding, primal-dual, greedy. (Ch 1 WS) |
Jan 18 |
Greedy and local search algorithms: Set cover, k-center, minimizing max-degree spanning tree. (WS 1.6, 2.2, 2.6). |
Jan 23 |
Greedy and local search algorithms: minimizing max-degree spanning trees, maximizing submodular functions. (WS 2.6, 2.5) |
Jan 25 |
Greedy and local search algorithms: maximizing nonmonotone submodular functions. Rounding data and dynamic programming: knapsack. (BFNS, WS 3.1) |
Jan 30 |
Rounding data and dynamic programming: knapsack. Scheduling identical parallel machines. (WS 3.1, 2.3, 3.2) |
Feb 1 |
Rounding data and dynamic programming: independent set in planar graphs. (WS 10.2) |
Feb 6 |
Deterministic and randomized rounding of linear programs: uncapacitated facility location. (WS 4.5, 5.8) |
Feb 8 |
Randomized rounding of linear programs: maximum satisfiability. (WS 5.1, 5.2, 5.4, 5.5) |
Feb 13 |
Deterministic and randomized rounding of linear programs: prize-collecting Steiner tree. Introduction to semidefinite programming. (WS 4.4, 5.7, 6.1) |
Feb 15 |
Randomized rounding of semidefinite programs: maximum cut. (WS 6.2) |
Feb 20 |
Randomized rounding of semidefinite programs: coloring 3-colorable graphs. (WS 6.5, 13.2) |
Feb 22 |
Randomized rounding of semidefinite programs: coloring 3-colorable graphs. The primal-dual method: shortest s-t paths, generalized Steiner tree. (WS 13.2, 7.3, 7.4) |
Feb 27 |
The primal-dual method: generalized Steiner tree, uncapacitated facility location. (WS 7.4, 7.6) |
March 1 |
Cuts and metrics: multiway cut. (WS 8.1, 8.2) |
March 6 |
Cuts and metrics: multicut. (WS 8.3) |
March 8 |
Cuts and metrics: tree metrics. (WS 8.5) |
March 13 |
Cuts and metrics: linear arrangement. Further deterministic LP rounding: minimum-cost bounded-degree spanning tree. (WS 8.7, 11.2) |
March 15 |
Further deterministic LP rounding: minimum-cost bounded-degree spanning tree. (WS 11.2) |
March 20 |
Further SDP rounding: unique games. (WS 13.3) |
March 22 |
The traveling salesman problem: The basics. (WS 2.4) |
March 27 |
Spring break. |
March 29 |
Spring break. |
April 3 |
The traveling salesman problem: LP-based analysis of Christofides' and Hoogeveen's algorithms. (see survey of Vygen) |
April 5 |
The traveling salesman problem: Gao's analysis of An-Kleinberg-Shmoys for Best-of-Many Christofides for s-t TSP path. |
April 10 |
The traveling salesman problem: Mömke and Svensson's algorithm for graphic TSP. (paper) |
April 17 |
Sparsest cut: Introduction, the Leighton-Rao algorithm, negative-type metrics. (see notes and notes) |
April 19 |
Sparsest cut: The SDP relaxation, the Arora-Rao-Vazirani algorithm. (see notes and notes, WS 15.4) |
April 24 |
Sparsest cut: Proof of the ARV Structure theorem. (see notes, WS 15.4) |
April 26 |
Open Problems. (WS 17, slides) |