CSE 597: Approximation Algorithms
Spring 2017

General Information

Time and location: Tuesday/Thursday 12:05PM - 1:20PM, 341 Deike
Instructor: Sofya Raskhodnikova
Office hours: Tuesdays, 1:30PM-2:30PM, IST 343F


CSE 565; STAT 318 or MATH 318 (specifically, familiarity with algorithms for network flow, linear programming, and discrete probability; comfort with mathematical proofs)

Course description

This course will cover the design and analysis of approximation algorithms for discrete optimization problems. Many problems in computer science and operations research can be modeled as discrete optimization problems, including packing, scheduling, facility location, internet routing, advertising, and network design. Most of these problems are NP-hard, and thus have no efficient exact algorithms unless P=NP. This course will focus on approximation algorithms: efficient algorithms that find provably near-optimal solutions. It will be organized around algorithmic techniques used for designing approximation algorithms, including greedy, local search, dynamic programming, deterministic and randomized rounding of linear and semidefininite programs, primal-dual, and metric embedding.


Primary: The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys, Cambridge University Press, New York, NY, USA, 2011.
Also: Approximation Algorithms, by Vijay V. Vazirani, Springer-Verlag, Berlin, 2001.


Students will be evaluated based on class participation (5%), solutions to homework assignments (45%), a midterm (20%) and a take-home final (30%).

Lecture Notes, Reading, Homework

DateSyllabusReading (reading in advance in bold)Handouts/Homework
Tu, Jan 10 Introduction. The Set Cover Problem: linear programming, deterministic rounding. WS, Chap. 1.1-1.3 General Information, Collaboration Policy
Th, Jan 12Set Cover: exploiting a dual solution, primal-dual, greedy. WS, Chap. 1.4-1.6 HW1 (due Wednesday): WS 1.5
Tu, Jan 17 Set Cover: greedy, randomized rounding. WS, Chap. 1.6-1.7
Th, Jan 19 Greedy algorithms and local search: scheduling with deadlines, k-Center. WS, Chap. 2.1-2.2 HW2 (due Wednesday): WS 1.1a, 2.1a
Tu, Jan 24 Scheduling on parallel machines, Traveling Salesman. WS, Chap. 2.3-2.4
Th, Jan 26 Lecture by Nithin Varma: Greedy algorithms and local search: float in bank accounts, min-degree spanning trees. WS, Chap. 2.5-2.6
Tu, Jan 31 Lecture by Jalaj Upadhyay: Finish min-degree spanning trees. WS, Chap. 2.6
Th, Feb 2 Edge coloring. Rounding data and dynamic programming: knapsack. WS, Chap. 2.7-3.1 HW3 (due Wednesday): WS 3.2
Tu, Feb 7 Rounding data and dynamic programming: knapsack, scheduling jobs on identical machines WS, Chap. 3.1-3.2
Th, Feb 9 Rounding data and dynamic programming: scheduling jobs on identical machines, bin packing. WS, Chap. 3.2-3.3 HW4 (due Wednesday): WS 3.7
Tu, Feb 14 Rounding data and dynamic programming: bin packing. Deterministic rounding of LPs: minimizing the sum of completion times WS, Chap. 3.3-4.1
Th, Feb 16 Deterministic rounding of LPs:minimizing the weighted sum of competion times, separation oracles WS, Chap. 4.2-4.3 HW5 (due Wednesday): WS 4.3
Tu, Feb 21 Prize-collecting Steiner tree WS, Chap. 4.4
Th, Feb 23 Uncapacitated facility location WS, Chap. 4.5 HW6 (due Wednesday): WS 4.6(a)
Tu, Feb 28 Bin packing WS, Chap. 4.6
Th, Mar 2 Sampling and derandomization, MAX-SAT WS, Chap. 5.1-5.3 HW7 (due Wednesday after Spring break): WS 5.1
March 4-12 Spring Break
Tu, Mar 14 Snow day: classes canceled
Th, Mar 16 Randomized rounding, the better of two solutions, Nonlinear randomized rounding WS, Chap. 5.4-5.6 HW8 (due Wednesday): WS 5.6b
Tu, Mar 21 Prize-Collecting Steiner Tree WS, Chap. 5.7
Th, Mar 23 Uncapacitated Facility Location WS, Chap. 5.8 HW9 (due Wednesday): WS 5.2b
Tu, Mar 28 Lecture by Nithin Varma: Scheduling a Single Machine WS, Chap. 5.9
Th, Mar 30 Useful probabilistic inequalities. Integer Multicommodity Flow. WS, Chap. 5.10-5.11 HW10 (due Wednesday)
Last week of classes Take-home final exam


Sample nameplate
Change the name to yours in this PPTX file, print it, and bring to class.
LaTeX resources
TexShop is a latex editor for the Mac platform; TexNiCenter is a tex editor for Windows; ShareLatex is a web-based latex system (allows you to avoid latex installation on your machine).
Not so short intro to latex; a latex tutorial.
Homework template files: tex, pdf, cls, jpg.

Sofya Raskhodnikova