
MS&E 319: Approximation
Algorithms
Instructor: Amin Saberi (650) 7047857 Time and Location: Tuesday
& Thursday 10:30AM11:50AM, Thornton Center, Rm 210 Office Hours: Thursdays 12 pm, Huang 309 Class website: http://msande319.stanford.edu
Course Description
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 NPhard. 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 nearoptimal solutions. Textbooks (available online)
Course load and Grading
Tentative OutlineCombinatorial
Algorithms _ Job
scheduling, set cover and vertex cover _ Traveling
Salesman Problems, kcenter LPbased
algorithms _ Linear
programming relaxations, randomized rounding and derandomization _ Primaldual
schema and its economic interpretations Semidefinite and
spectral relaxations _ Low
distortion metric embedding, tree metrics, and treecut packing _ Sumofsquares
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 #Phard problems _ Selfreducibility,
Markov chain Monte Carlo methods, and Importance Sampling Class OutlineWeek 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 Kmedian (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 WilliamsonShmoys) á
3Coloring Problem
(Section 6.5 of WilliamsonShmoys) Week 4 (Oct. 18
& 20) á Multiway
Cut and kCut (Chapter 4 of Vazirani) á Cuts and
Metrics (Sections 8.18.3 of WilliamsonShmoys) á Metrics,
Cut Packings, and l1embeddability (Chapter 21 of Vazirani,
Section 15.1 of WilliamsonShmoys) 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, MonteCarlo
Approximation Algorithms for Enumeration Problems. Week 6 (Nov. 1
& 3) á Random
walks and electrical networks: Doyle and SnellŐs excellent exposition á Matrixtree
theorem: see the notes
from my algebraic graph theory class.
Week 7 (Nov. 8
& 10) á CheegerŐs inequality: see Luca TrevisanŐs notes here
and there.
Also LovaszŐs excellent survey. á Expansion
of random regular graphs: See LucaŐs simple
calculation as well as D.
EllisŐs more extensive
notes. Week 8 (Nov. 15
& 17) á Sum of
Square Method: in class we followed these notes.
You can also see this survey as
well as this course on the
subject. Week 10 (Nov. 29
& Dec .1) á Graph sparsification: see my notes as
well as the paper by Spielman and Srivastava. Problem Sets

