MS&E 319: Approximation Algorithms
Instructor: Amin Saberi
Time and Location: Tuesday & Thursday 10:30AM-11:50AM, Thornton Center, Rm 210
Office Hours: Thursdays 1-2 pm, Huang 309
Class website: http://msande319.stanford.edu
Interesting discrete optimization problems are everywhere, from
classic operations research problems, such as scheduling, facility location,
and traveling salesman problems, to computer science problems in Internet
routing, data mining, social network analysis, and advertising. Yet most
interesting discrete optimization problems are NP-hard. Thus unless P = NP,
there are no efficient algorithms to find optimal solutions to such problems.
This course shows how to design approximation algorithms: efficient
algorithms that find provably near-optimal solutions.
Textbooks (available online)
Course load and Grading
_ Job scheduling, set cover and vertex cover
_ Traveling Salesman Problems, k-center
_ Linear programming relaxations, randomized rounding and de-randomization
_ Primal-dual schema and its economic interpretations
Semi-definite and spectral relaxations
_ Low distortion metric embedding, tree metrics, and tree-cut packing
_ Sum-of-squares method and applications
_ Graph sparsification and electrical networks
Rounding by Sampling and maximum entropy distributions
_ Traveling Salesman problems, Assignment problems
Approximate counting and sampling for #P-hard problems
_ Self-reducibility, Markov chain Monte Carlo methods, and Importance Sampling
Week 1 (Sept. 26 & 28)
á Introduction (Chapter 1 of Vazirani). Maximum Satisfiability (Chapter 16 of Vazirani)
á Scheduling on Unrelated Parallel Machines (Chapter 17 of Vazirani). See also the lecture notes.
Week 2 (Oct. 4 & 6)
á Set cover from three different points of view (Chapters 2, 13, and 15 of Vazirani)
á Facility Location and K-median (Chapters 24 and 25 of Vazirani)
Week 3 (Oct. 11 & 13)
á Semidefinite Programming and Maximum Cut (Chapter 26 of Vazirani).
á Randomized Rounding of Semidefinite Programs (Chapter 6 of Williamson-Shmoys)
á 3-Coloring Problem (Section 6.5 of Williamson-Shmoys)
Week 4 (Oct. 18 & 20)
á Multiway Cut and k-Cut (Chapter 4 of Vazirani)
á Cuts and Metrics (Sections 8.1-8.3 of Williamson-Shmoys)
á Metrics, Cut Packings, and l1-embeddability (Chapter 21 of Vazirani, Section 15.1 of Williamson-Shmoys)
Week 5 (Oct. 25 & 27)
á Counting problems: Counting DNF Solutions and network reliability (Section 28.1 and 28.2 of Vazirani)
á Approximate counting and approximate sampling: M. Jerrum, L. Valiant, V. Vazirani, Random Generation of Combinatorial Structures from a Uniform Distribution.
á R. Karp, M. Luby, N. Madras, Monte-Carlo Approximation Algorithms for Enumeration Problems.
Week 6 (Nov. 1 & 3)
á Random walks and electrical networks: Doyle and SnellŐs excellent exposition
á Matrix-tree theorem: see the notes from my algebraic graph theory class.
Week 7 (Nov. 8 & 10)
Week 8 (Nov. 15 & 17)
Week 10 (Nov. 29 & Dec .1)