ORIE 6334: Approximation Algorithms

Spring 2014

Instructor Information

Instructor: David P. Williamson Rhodes 236 M 1:30-2:30, W 11-12, and by appointment 255-4883 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) Introduction to the techniques: Set cover. Primal-dual, LP rounding, Greedy algorithms. (Ch 1 WS). Greedy and local search algorithms: k-center, maximizing submodular functions. (WS 2.2, 2.5) Greedy and local search algorithms: maximizing nonmonotone submodular functions, minimum maximum-degree trees (BFNS, WS 2.6) Greedy and local search algorithms: minimum maximum-degree trees. Rounding data and dynamic programming: knapsack. (WS 2.6, 3.1) Rounding data and dynamic programming: independent set in planar graphs. (WS 10.2) Deterministic and randomized rounding of linear programs: uncapacitated facility location. (WS 4.5, 5.8) Randomized rounding of linear programs: maximum satisfiability. (WS 5.1, 5.2, 5.4, 5.5) Randomized rounding of semidefinite programs: maximum cut. (WS 6.1, 6.2) Randomized rounding of semidefinite programs: coloring 3-colorable graphs. (WS 6.5, 13.2) The primal-dual method: set cover, shortest s-t paths, generalized Steiner tree. (WS 7.1, 7.3, 7.4) The primal-dual method: generalized Steiner tree, uncapacitated facility location. (WS 7.4, 7.6) Greedy and local search algorithms: uncapacitated facility location. (see Gupta) Cuts and metrics: multiway cut. (WS 8.1, 8.2) Cuts and metrics: multicut. Tree metrics. (WS 8.3, 8.5) Cuts and metrics: tree metrics (WS 8.5) No class. No class: Spring break. No class: Spring break. Deterministic rounding of linear programs: Minimum-cost bounded-degree spanning trees (WS 11.2). Deterministic rounding of linear programs: Minimum-cost bounded-degree spanning trees (WS 11.2). Greedy and local search algorithms: Maximizing a nonmonotone submodular function subject to a matroid constraint (Filmus, Ward). Randomized rounding of semidefinite programs: Unique games (WS 13.3). The traveling salesman problem: Christofides' and Hoogeveen's algorithms. Best-of-Many Christofides. (see survey of Vygen) The traveling salesman problem: Gao's algorithm for graphic s-t TSP path. (paper) The traveling salesman problem: Mömke and Svensson's algorithm for graphic TSP. (paper) The traveling salesman problem: Gao's reanalysis of An-Kleinberg-Shmoys and Sebő for Best-of-Many Christofides for s-t TSP path. (paper) Open problems.