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

Office: | Rhodes 236 |

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

Office phone: | 255-4883 |

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

Sept 1 | Introduction to approximation algorithms. Introduction to the techniques: set cover. LP rounding, dual rounding. (Chap 1 of WS) |
---|---|

Sept 3 | Introduction to the techniques: set cover: Primal-dual, greedy. Greedy and local search algorithms: Maximizing bank float (Chap 1, 2 of WS) |

Sept 8 | Greedy and local search algorithms: Maximizing submodular functions. Minimum maximum-degree spanning trees. (Chap 2 of WS) |

Sept 10 | Greedy and local search algorithms: Minimum maximum-degree spanning trees. Rounding data and dynamic programming: knapsack (Chap 2, 3 of WS) |

Sept 15 | Rounding data and dynamic programming: knapsack, bin packing. (Chap 3 of WS) |

Sept 17 | Deterministic rounding of linear programs: bin packing. (Chap 4 of WS) |

Sept 22 | Randomized rounding of linear programs: the maximum satisfiability problem. (Chap 5 of WS) |

Sept 24 | Randomized rounding of linear programs: the maximum satisfiability problem. Randomized rounding of semidefinite programs: the maximum cut problem (Chaps 5, 6 of WS) |

Sept 29 | Randomized rounding of semidefinite programs: the maximum cut problem. Quadratic programs. (Chap 6 of WS) |

Oct 1 | Deterministic and randomized rounding of linear programs: the uncapacitated facility location problem (Chaps 4,5 of WS) |

Oct 6 | The primal-dual method: Generalized Steiner tree. (Chap 7 of WS) |

Oct 8 | The primal-dual method: the uncapacitated facility location problem. (Chap 7 of WS) |

Oct 15 | Cuts and metrics: the multiway cut problem. (Chap 8 of WS) |

Oct 20 | Cuts and metrics: the multicut problem. (Chap 8 of WS) |

Oct 22 | Cuts and metrics: probabilistic embedding of metrics into tree metrics. (Chap 8 of WS) |

Oct 27 | Further deterministic rounding: bounded-degree spanning trees. (Chap 11 of WS) |

Oct 29 | Further deterministic rounding: bounded-degree spanning trees. (Chap 11 of WS) |

Nov 3 | Further greedy and local search: uncapacitated facility location. (Chap 9 of WS) |

Nov 5 | Further greedy and local search: the k-median problem. (Chap 9 of WS) |

Nov 10 | Further rounding of semidefinite programs: Coloring 3-colorable graphs. (Chaps 6, 13 of WS) |

Nov 12 | Further rounding of semidefinite programs: Coloring 3-colorable graphs. Unique games. (Chap 13 of WS) |

Nov 17 | Further rounding of semidefinite programs: Unique games. (Chap 13 of WS) |

Nov 19 | Further deterministic rounding: Survivable network design. (Chap 11 of WS) |

Nov 24 | Further cuts and metrics: Oblivious routing. (Chap 15 of WS) |

Dec 1 | Further cuts and metrics: the minimum bisection problem. (Chap 15 of WS) |

Dec 3 | Course conclusion and open problems. |