Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Fwd: course announcement for approx. algs.

Gregory Valiant gvaliant at cs.stanford.edu
Mon Sep 26 17:17:13 PDT 2016


Hi Friends,
Amin Saberi will be teaching a graduate Approximation Algorithms class
this quarter--see the course info below.
Cheers,
-g
---------------

MS&E 319: Approximation Algorithms
TuTh 10:30AM-11:50AM
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
of research.

Textbooks:
- 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 mailing list