Instructor: | David P. Williamson |
---|---|

Office hours (Soda 329): | Tuesdays 2:30-3:30PM, Thursdays 9:30-10:30AM |

Email: | My three initials AT berkeley.edu |

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