MS&E 319: Approximation Algorithms

 

Instructor: Amin Saberi
Huang Engineering Center, #309

saberi@stanford.edu

(650) 704-7857

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

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 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.

The course is organized around central techniques for designing approximation algorithms. Each week a new technique is introduced and illustrated through several applications, covering greedy and local search, linear and semidefinite relaxations, and rounding using randomization, metric embedding, and sampling.

The course starts from basic concepts assuming only familiarity with network flows, linear programming, and discrete probability and moves at a fast pace to cover more recent contributions in this active area of research.

 

Textbooks (available online)

 

Course load and Grading

 

  • Homework: 4 homework assignments of 20% each.
  • Final project: 30%. (if you get more than 100, you will get an A+).

 

Tentative Outline

 

Combinatorial Algorithms

_      Job scheduling, set cover and vertex cover

_      Traveling Salesman Problems, k-center

LP-based algorithms

_      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

Class Outline

 

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)  

á      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