ORIE 634: Approximation Algorithms

Fall 2006

Instructor Information

Instructor: David P. Williamson
Office: Rhodes 236
Office hours: By appointment
Office phone: 255-4883
Email: My three initials AT cs.cornell.edu

Overview

The course meets Tuesdays and Thursdays in Upson 109 from 11:40 to 12:55. This course will introduce students to the fundamentals in the design and analysis of approximation algorithms. The focus will be on a core set of techniques: greedy algorithms; local search; rounding, scaling, and dynamic progamming; deterministic and randomized rounding of linear programs; semidefinite programming; cuts and metrics; and the primal-dual method. The course will start with some elementary applications of the techniques to central problems in discrete optimization, and then continue with more recent and advanced applications.

Handouts

Handout 1: Course Information
Course Notes on Approximation Algorithms

Lectures

Aug 24 Introduction to approximation algorithms. Introduction to the techniques: set cover. LP rounding, dual rounding. (Chap 1 of SW)
Aug 29 Introduction to the techniques: set cover. Primal-dual. Greedy. Greedy algorithms: k-center. (Chs 1,2 of SW)
Aug 31 Greedy algorithms: k-center, float maximization. Local search algorithms: minimum-degree spanning tree (Ch 2 of SW)
Sept 5 Local search: minimum-degree spanning trees. Rounding data and dynamic programming: knapsack. (Chs 2,3 of SW)
Sept 7 Rounding data and dynamic programming: bin packing. (Ch 3 of SW)
Sept 12 LP rounding: bin packing. (Ch 4 of SW)
Sept 14 Randomization: MAX SAT. (Ch 5 of SW)
Sept 19 Deterministic and randomized rounding: Uncapacitated facility location (Chs 4,5 of SW)
Sept 21 Deterministic and randomized rounding: Uncapacitated facility location. Prize-collecting Steiner tree (Chs 4,5 of SW)
Sept 26 Deterministic and randomized rounding: Prize-collecting Steiner tree. Intro to semidefinite programming. (Chs 4,5 of SW)
Sept 28 Semidefinite programming: Max Cut. Correlation clustering. (Ch 5 of SW)
Oct 3 Semidefinite programming: Coloring 3-colorable graphs. Primal-dual method: set cover review (Chs 5, 7 of SW)
Oct 5 Primal-dual method: Feedback vertex set. Shortest s-t path. Generalized Steiner tree. (Ch 7 of SW)
Oct 12 Primal-dual method: Generalized Steiner tree. Uncapacitated facility location. (Ch 7 of SW)
Oct 17 Primal-dual method: Uncapacitated facility location. Cuts and metrics: Multiway cut. (Chs 6,7 of SW)
Oct 19 Cuts and metrics: Multiway cut. Multicut. (Ch 6 of SW)
Oct 24 Cuts and metrics: Multicut. Balanced cut. (Ch 6 of SW)
Oct 26 Cuts and metrics: Balanced cut. Tree metrics. Buy-at-bulk network design. (Ch 6 of SW)
Oct 31 Cuts and metrics: Buy-at-bulk network design. Probabilistic approximation of metrics by tree metrics. (Ch 6 of SW)
Nov 2 Cuts and metrics: Probabilistic approximation of metrics by tree metrics. Primal-dual revisited: k-median. (Ch 6 of SW)
Nov 7 Primal-dual revisited: k-median. Local search revisited: k-median.
Nov 9 Local search revisited: k-median. Cuts and metrics revisited: sparsest cut and l_1 embeddings.
Nov 14 Cuts and metrics revisited: sparsest cut and l_1 embeddings.
Nov 16 Deterministic rounding revisited: Survivable network design.
Nov 21 Deterministic rounding revisited: Survivable network design. Brief overview of matroids.
Nov 28 Deterministic rounding revisited: Minimum-cost degree-k spanning trees.
Nov 30 Conclusion.

Problem Sets