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

Office: | Rhodes 236 |

Office hours: | M 1:30-2:30, W 11-12, and by appointment |

Office phone: | 255-4883 |

Email: | My three initials AT cs.cornell.edu |

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