Jan 28 |
Introduction to approximation algorithms. Introduction to the techniques: Set cover. LP rounding. (Ch 1 WS) |
Jan 30 |
Introduction to the techniques: Set cover. Primal-dual, LP rounding, Greedy algorithms. (Ch 1 WS). |
Feb 4 |
Greedy and local search algorithms: k-center, maximizing submodular functions. (WS 2.2, 2.5) |
Feb 6 |
Greedy and local search algorithms: maximizing nonmonotone submodular functions, minimum maximum-degree trees (BFNS, WS 2.6) |
Feb 11 |
Greedy and local search algorithms: minimum maximum-degree trees. Rounding data and dynamic programming: knapsack. (WS 2.6, 3.1) |
Feb 13 |
Rounding data and dynamic programming: independent set in planar graphs. (WS 10.2) |
Feb 20 |
Deterministic and randomized rounding of linear programs: uncapacitated facility location. (WS 4.5, 5.8) |
Feb 25 |
Randomized rounding of linear programs: maximum satisfiability. (WS 5.1, 5.2, 5.4, 5.5) |
Feb 27 |
Randomized rounding of semidefinite programs: maximum cut. (WS 6.1, 6.2) |
March 4 |
Randomized rounding of semidefinite programs: coloring 3-colorable graphs. (WS 6.5, 13.2) |
March 6 |
The primal-dual method: set cover, shortest s-t paths, generalized Steiner tree. (WS 7.1, 7.3, 7.4) |
March 11 |
The primal-dual method: generalized Steiner tree, uncapacitated facility location. (WS 7.4, 7.6) |
March 13 |
Greedy and local search algorithms: uncapacitated facility location. (see Gupta) |
March 18 |
Cuts and metrics: multiway cut. (WS 8.1, 8.2) |
March 20 |
Cuts and metrics: multicut. Tree metrics. (WS 8.3, 8.5) |
March 25 |
Cuts and metrics: tree metrics (WS 8.5) |
March 27 |
No class. |
April 1 |
No class: Spring break. |
April 3 |
No class: Spring break. |
April 8 |
Deterministic rounding of linear programs: Minimum-cost bounded-degree spanning trees (WS 11.2). |
April 10 |
Deterministic rounding of linear programs: Minimum-cost bounded-degree spanning trees (WS 11.2). |
April 15 |
Greedy and local search algorithms: Maximizing a nonmonotone submodular function subject to a matroid constraint (Filmus, Ward). |
April 17 |
Randomized rounding of semidefinite programs: Unique games (WS 13.3). |
April 22 |
The traveling salesman problem: Christofides' and Hoogeveen's algorithms. Best-of-Many Christofides. (see survey of Vygen) |
April 24 |
The traveling salesman problem: Gao's algorithm for graphic s-t TSP path. (paper) |
April 29 |
The traveling salesman problem: Mömke and Svensson's algorithm for graphic TSP. (paper) |
May 1 |
The traveling salesman problem: Gao's reanalysis of An-Kleinberg-Shmoys and Sebő for Best-of-Many Christofides for s-t TSP path. (paper) |
May 6 |
Open problems. |