Search Mailing List Archives
[theory-seminar] Fwd: course announcement for approx. algs.
gvaliant at cs.stanford.edu
Mon Sep 26 17:17:13 PDT 2016
Amin Saberi will be teaching a graduate Approximation Algorithms class
this quarter--see the course info below.
MS&E 319: Approximation Algorithms
Thornton Center (Terman Annex), Rm 210
Instructor: Amin Saberi
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 linear and
semidefinite relaxations, spectral methods, 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
- Approximation Algorithms, by Vijay V. Vazirani, Springer-Verlag, Berlin, 2001.
- The Design of Approximation Algorithms, David P. Williamson and
David B. Shmoys, Cambridge University Press, New York, NY, USA, 2011.
More information about the theory-seminar