CS 583: Approximation Algorithms, Spring 2018
Course Summary
Approximation algorithms for NPhard problems are polynomial time heuristics that have guarantees on the quality of their solutions. Such algorithms are one robust way to cope with intractable problems that arise in many areas of Computer Science and beyond. In addition to being directly useful in applications, approximation algorithms allow us to explore the structure of NPhard problems and distinguish between different levels of difficulty that these problems exhibit in theory and practice. A rich algorithmic theory has been developed in this area and deep connections to several areas in mathematics have been forged. The first third to half of the course will provide a broad introduction to results and techniques in this area with an emphasis on fundamental problems and widely applicable tools. The second half of the course will focus on more advanced and specialized topics.
Administrative Information
Lectures: Tue, Thu 9.30am10.45am in Siebel Center 1105.
Instructor: Chandra Chekuri, 3228 Siebel Center, (chekuri at)
Teaching Assistant: Vivek Madan, 3238A Siebel Center, (vmadan2 at)
Office Hours (Chandra): Thu 3.454.45pm, 3228 Siebel
Office Hours (Vivek): Tue 23pm, Siebel 3rd floor lounge
Grading Policy: There will be 6 homeworks, roughly once every two weeks. I expect all students to do the first 4. Students have the option of doing a course project in lieu of the last two homeworks (more information on topics forthcoming). Course projects could involve research on a specific problem or topic, a survey of several papers on a topic (summarized in a report and/or talk), or an application of approximation algorithms to some applied area of interest including experimental evaluation of specific algorithms. You can consult the instructor if you wish to do less home works for a
longer course project
Prerequisites: This is a graduate level class and a reasonable background in algorithms and discrete mathematics would be needed. Officially the prerequisite is CS 573 (now Theory II) or equivalent. Knowledge and exposure to probability and linear programming is necessary. The instructor will try to make the material accessible to nontheory students who might be interested in applications. Consult the instructor if you have questions.
Study material:

Recommended text books

Another useful book: Approximation Algorithms for NPhard Problems, edited by Dorit S. Hochbaum, PWS Publishing Company, 1995.
 Iterative Methods in Combinatorial Optimization by Lau, Ravi and Singh.

Geometric Approximation Algorithms by Sariel HarPeled, American Mathematical Society, 2011

Notes and slides from previous editions of the course: Spring 2016, Fall 2013, Spring 2011, Spring 2009 and Fall 2006.

Books on related topics: Combinatorial Optimization (Schrijver), Randomized Algorithms (MotwaniRaghavan), The Probabilistic Method (AlonSpencer)

Lecture notes from various places: CMU (GuptaRavi), CMU2 (Gupta), EPFL (Svensson) .

Jeff Erickson's algorithms lecture notes, old homeworks and exams

Notes and pointers to topics in combinatorial optimization from Chandra's course in Spring 2010
Homework:
Homework 0 (tex file) given on 01/16/2018, due in class on Thursday 01/25/2018.
Homework 1 (tex file) given on 01/25/2018, due on Thursday 02/08/2018.
Homework 2 (tex file) given on 02/08/2018, due on Thursday 02/22/2018.
Homework 3 (tex file) given on 02/23/2018, due on Thursday 03/08/2018.
Homework 4 (tex file) given on 03/10/2018, due on Thursday 03/30/2018.
Homework 5 (tex file) given on 04/05/2018, due on Friday 04/20/2018.
Homework 6 (tex file) given on 04/20/2018, due on Friday 05/04/2018.
Lectures:
Warning: Notes may contain errors. Please bring those to the attention of the instructor.

Lecture 1: 1/20/2016, Introduction, Covering problems, Greedy for Set Cover

Chapter 1 in WilliamsonShmoys book

Chapters 1, 2 in Vazirani book
 Intro and Covering

Lecture 2: 1/18/2016, LP rounding for vertex cover, set cover

Chapter 1 in WilliamsonShmoys book

Chapters 13, 14, 15 in Vazirani book
 Covering

Lecture 3: 1/23/2016, Dualfitting analysis for Set Cover, Additive vs Relative approx, Dominating Set Hardness
 Chapter 1 in WilliamsonShmoys book for Set Cover, Chapter 16 on hardness

Chapters 13 in Vazirani book for Set Cover, Chapter 29 on Hardness of Approximation
 Covering

Lecture 4: 1/25/2018, PTAS and FPTAS for Knapsack

Chapter 3 in WilliamsonShmoys book

Chapter 8 in Vazirani book

Notes from the past.
Lecture 6

Lecture 5: 1/30/2018, Packing problems: maximum independent set, packing integer programs
 Notes
 Paper of Borodin and Ye
on elimination graphs and generalization.

Lecture 6: 2/1/2018, Finish
packing

Lecture 7: 2/6/2018, Scheduling problems. Graham's list scheduling and PTAS for parallel machines

Lecture 8: 2/8/2018,
Multiprocessor scheduling with precedence constraints, Bin Packing

Lecture 9: 2/13/2018,
Unrelated machine scheduling and congestion minimization: randomized rounding and Chernoff bounds
 Chapter 5.11 in WilliamsonShmoys book for congestion minimization
 Notes on Chernoff bounds from Sariel HarPeled. Also a cheat sheet.
 For finer results on congestion minimization and related problems see Srinivasan's paper as well as
recent results on LovaszLocalLemma starting with MoserTardos paper and applications/refinements in paper of
Haeupler, Saha and Srinivasan.

Lecture 10: 2/15/2018,
Unrelated machine scheduling
 Notes from the past.
 Short notes on rank lemma. See also Chapter 2 in book by Lau, Ravi, Singh (linked above).
 Chapter 11.1 in WilliamsonShmoys book for generalized assignment

Lecture 11: 2/20/2018,
Intro to local search: Max Cut and Submodular Function Maximization.
 Notes from the past on local search.
 Chapters 2, 9 in WilliamsonShmoys book for local search

Lecture 12: 2/22/2018,
kcenter and start facility location
 Chapter 2 in WilliamsonShmoys book for kcenter (Gonzalez's algorithm)
 Chapter 5 in Vazirani book for kcenter (the bottleneck algorithm)

Lecture 13: 2/27/2018,
Uncapacitated facility location: nonmetric and metric
 Chapter 4.5 in WilliamsonShmoys book. Also see Chapter 9 for local search and a greedy algorithm.

Lecture 14: 3/1/2018,
Local search for kmedian
 Chapter 9 in WilliamsonShmoys book.

Lecture 15: 3/6/2018,
Start Network Design, Steiner Tree, Metric TSP.
 Notes from the past. (Steiner tree, TSP)
 Chapters 2, 9 in WilliamsonShmoys book for TSP and Steiner tree

Lecture 16: 3/8/2018,
ATSP, Intro to primal dual via vertex cover.
 Chapter 7 in WillamsonShmoys
 Chapters 12, 15 in Vazirani
 A survey by Jens Vygen on recent exciting development on MetricTSP and ATSP and related problems.
 A recent breakthrough paper by Svensson, Tarnawski and Vegh which gives the first constant factor approximation for ATSP (via LP).

Lecture 17: 3/13/2018 (by Vivek Madan),
More on primal dual: feedback vertex set and shortest paths.
 Chapter 7 in WillamsonShmoys

Lecture 18: 3/15/2018 (by Vivek Madan),
Primal dual for Steiner forest.
 Chapter 7 in WillamsonShmoys
 Chapter 22 in Vazirani

Lecture 19: 3/27/2018,
Steiner Network, Abstract Network Design.
 Survey by Goemans and Williamson on primaldual for network design

Lecture 20: 3/29/2018,
Covering skewsupermodular functions, iterated rounding approach of Jain.
 Chapter 11 in WilliamsonShmoys book
 Chapter 23 in Vazirani book

Lecture 21: 4/3/2018,
Continue previous lecture.

Lecture 22: 4/5/2018,
Finish counting argument for Steiner network iterated rounding. Intro
to graph cut and partition problems.
 Note of Chandra and Thapanapong
that has alternate proof for the counting arugment.

Lecture 23: 4/10/2018,
2approx for Multiway Cut: edge, node, directed.
 Notes from Fall 2006 on metric
methods and edge multiway cut.
 Chapter 8 in WilliamsonShmoys book
 Chapters 4, 19 in Vazirani book
 Recent paper of Chandra and Vivek
on simple rounding for directed multiway cut

Lecture 24: 4/12/2018,
1.5 approx for multiway cut via CKR relaxation.
 Notes
 Chapter 8 in WilliamsonShmoys book
 Chapter 19 in Vazirani book
 Paper on submodular multiway partition
 Article on continuous extensions of submodular set functions

Lecture 25: 4/17/2018,
Multicut, O(log k) approximation/flowcut gap, lower bound via expanders.
 Notes from 2009 on multicut. The algorithm in the notes is different from the region growing ones given in the books below.
 Chapter 8 in WilliamsonShmoys book
 Chapter 20 (also Chapter 18) in Vazirani book

Lecture 26: 4/19/2018, Finish multicut, introduce sparsest cut.

Lecture 27: 4/22/2016,
Intro to metric embeddings, Sparsest cut via l_1 embeddings and tree embeddings.
 Chapter 21 in Vazirani book
 Chapter 15 in WilliamsonShmoys book.
 Lecture
notes on metric embeddings by Matousek. Also a chapter on
emebdding finite metric spaces in normed spaces.
 Notes on tree embeddings from CMU class by Gupta and Ravi.

Lecture 28: 4/24/2018,
Intro to SDP, MaxCut.
 Chapter 6 in WilliamsonShmoys book.
 Chapter 26 in Vazirani book.
 Notes from 2006.

Lecture 29: 5/1/2018,
Constraint satisfaction problems (CSPs), hardness of approximation, closing thoughts.
 Chapter 16 in WilliamsonShmoys book.
 Chapters 16, 29 in Vazirani book.
 Canonical LP and Canonical SDP for CSPs : lecture notes from CMU course.
