ORIE 6334: Approximation Algorithms

Spring 2014

Instructor Information

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

Overview

The course meets Tuesdays and Thursdays in Rhodes 253 from 1:25-2:40. 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

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.

Problem Sets