CS 294: Approximation Algorithms

Spring 2018

Instructor Information

Instructor: David P. Williamson
Office hours (Soda 329): Tuesdays 2:30-3:30PM, Thursdays 9:30-10:30AM
Email: My three initials AT berkeley.edu

Overview

The course meets Tuesdays and Thursdays in Soda 310 from 3:30-4:59. 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 16 Introduction to approximation algorithms. Introduction to the techniques: Set cover. LP rounding, dual rounding, primal-dual, greedy. (Ch 1 WS)
Jan 18 Greedy and local search algorithms: Set cover, k-center, minimizing max-degree spanning tree. (WS 1.6, 2.2, 2.6).
Jan 23 Greedy and local search algorithms: minimizing max-degree spanning trees, maximizing submodular functions. (WS 2.6, 2.5)
Jan 25 Greedy and local search algorithms: maximizing nonmonotone submodular functions. Rounding data and dynamic programming: knapsack. (BFNS, WS 3.1)
Jan 30 Rounding data and dynamic programming: knapsack. Scheduling identical parallel machines. (WS 3.1, 2.3, 3.2)
Feb 1 Rounding data and dynamic programming: independent set in planar graphs. (WS 10.2)
Feb 6 Deterministic and randomized rounding of linear programs: uncapacitated facility location. (WS 4.5, 5.8)
Feb 8 Randomized rounding of linear programs: maximum satisfiability. (WS 5.1, 5.2, 5.4, 5.5)
Feb 13 Deterministic and randomized rounding of linear programs: prize-collecting Steiner tree. Introduction to semidefinite programming. (WS 4.4, 5.7, 6.1)
Feb 15 Randomized rounding of semidefinite programs: maximum cut. (WS 6.2)
Feb 20 Randomized rounding of semidefinite programs: coloring 3-colorable graphs. (WS 6.5, 13.2)
Feb 22 Randomized rounding of semidefinite programs: coloring 3-colorable graphs. The primal-dual method: shortest s-t paths, generalized Steiner tree. (WS 13.2, 7.3, 7.4)
Feb 27 The primal-dual method: generalized Steiner tree, uncapacitated facility location. (WS 7.4, 7.6)
March 1 Cuts and metrics: multiway cut. (WS 8.1, 8.2)
March 6 Cuts and metrics: multicut. (WS 8.3)
March 8 Cuts and metrics: tree metrics. (WS 8.5)
March 13 Cuts and metrics: linear arrangement. Further deterministic LP rounding: minimum-cost bounded-degree spanning tree. (WS 8.7, 11.2)
March 15 Further deterministic LP rounding: minimum-cost bounded-degree spanning tree. (WS 11.2)
March 20 Further SDP rounding: unique games. (WS 13.3)
March 22 The traveling salesman problem: The basics. (WS 2.4)
March 27 Spring break.
March 29 Spring break.
April 3 The traveling salesman problem: LP-based analysis of Christofides' and Hoogeveen's algorithms. (see survey of Vygen)
April 5 The traveling salesman problem: Gao's analysis of An-Kleinberg-Shmoys for Best-of-Many Christofides for s-t TSP path.
April 10 The traveling salesman problem: Mömke and Svensson's algorithm for graphic TSP. (paper)
April 17 Sparsest cut: Introduction, the Leighton-Rao algorithm, negative-type metrics. (see notes and notes)
April 19 Sparsest cut: The SDP relaxation, the Arora-Rao-Vazirani algorithm. (see notes and notes, WS 15.4)
April 24 Sparsest cut: Proof of the ARV Structure theorem. (see notes, WS 15.4)
April 26 Open Problems. (WS 17, slides)

Problem Sets