Instructor: Ashish Goel (Office hours by appointment)
Auditors etc. with a valid Stanford email address can subscribe to msande319-win0405-guests using majordomo (login to http://lists.stanford.edu for instructions) to get course announcements.
Scribed notes (Stanford access only)
Many, if not most, real-life optimization problems are hard to solve. The hardness may be computational (eg. the problem may be NP-hard), may relate to imperfect information (as in online or non-clairvoyant algorithms), or may be due to multiple conflicting objectives. We will use combinatorial and mathematical programming techniques to derive approximation algorithms for a broad spectrum of optimization problems. The class will be structured around broadly applicable techniques, and we will see several classical and recent applications of these techniques. We will point out the main open research problems related to each topic that we discuss.
The syllabus below is subject to change as the class progresses.
Review of basic concepts: LP duality, complementary slackness, convex optimization via separation oracles, NP-completeness
Greedy algorithms: Vertex/Set Cover, Sub-modular Function Maximization
Application: Maximizing the spread of influence through a social network
Undirected Traveling Salesman Problem and the Held-Karp bounds
Undirected Minimum Steiner Tree
Embedding metric spaces into trees
Application: Buy-At-Bulk Network Design
Application: Group Steiner Trees
The Rent-or-Buy problem
Fairness in load balancing and resource allocation
Data aggregation in sensor networks
Shallow Light Trees
Zero-One Knapsack and Bin Packing
Application: Constrained Shortest Paths
Directed Steiner Trees or Geometric PTASs (polynomial time approximation schemes)
Bourgain’s embeddings of metric spaces into normed spaces
The Sparsest Cut Problem, with applications
Semi-Definite Programming and Max-Cut
The l1-l2 gap, with algorithmic applications
Open problem: embedding minor-closed graphs
Flow-time with and without augmentation
Facility Location and the k-Median Problem
Steiner Network Design (time permitting)
MS&E 212 or CS 161 or CS 261 or prior exposure to algorithms, graph theory, NP-completeness, and linear programming.
There will be several HWs (4-6) and a take-home exam. The HWs will have a total weight of 70% and the exam will have a weight of 30%. Students may choose to do an optional project. Discussion is allowed and encouraged on HWs, as long as each student writes his or her own answers and clearly acknowledges the contribution of other students.
In addition, each student will be expected to scribe 1-2 lectures.
The final exam will be given out on Mar 10th and will be due back on Mar 14th.
Required textbook: Approximation Algorithms, Vijay V.Vazirani, Springer 2003
Reading list (under constant construction, and only for material that is not covered extensively by the text):
Approximation algorithms is by now a vast discipline, and no one quarter course can do justice to it. Some of the important topics that we will not touch upon are randomized rounding, approximate counting, online algorithms, and lower-bounds. Please be on the lookout for classes that cover this material.
We will maintain a reverse chronological list summarizing the announcements made on the class email list.
2/28/2005: The combined HWs 2 and 3 are now online. Due 3/10/2005.
Approximations Bee: Terman 453, Fri Feb 25th, 12:00-1:30.
1/18/2005: Scribed lecture notes for the first three lectures are online. These are made by students without any editorial intervention by the instructor.
1/18/2005: Homework 1 is now online. Due 1/127/5.
1/6/2005: Handout 1 (tell us abouty ourself) is now online. Due 1/11.
1/6/2005: We have requested that the text-book be placed on reserve in the MATH-CS library. It might take a few days for this to happen.