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)

Problem Sets