ORIE 6334: Approximation Algorithms

Fall 2009

Instructor Information

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

Overview

The course meets Tuesdays and Thursdays in Hollister 320 from 1:10-2:25. 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; the primal-dual method; and cuts and metrics. 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

Lectures

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.

Problem Sets