Approximation Algorithms for Optimization Problems.

MS&E 319
Winter 2004-05, Stanford University

TTh 4:15-5:30, Terman 453

 

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.

 

*  Class objective

*  Detailed syllabus

*  Pre-requisites

*  Workload/Grading info

*  Textbook and reading list

*  Handouts

*  What we will not teach

*  Scribed notes (Stanford access only)

*  Announcements

 

---

 

Class objective:

 

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.

 

---

 

Detailed syllabus:

 

The syllabus below is subject to change as the class progresses.

 

  1. Warming up (2 lectures)

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

  1. Tree based approximations (3 lectures)

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

  1. More on Buy-at-Bulk (1 lecture)

The Rent-or-Buy problem

  1. Simultaneous Optimization (2 lectures)

Fairness in load balancing and resource allocation

Data aggregation in sensor networks

Shallow Light Trees

  1. Dynamic programming techniques (2 lectures)

Zero-One Knapsack and Bin Packing

Application: Constrained Shortest Paths

Directed Steiner Trees or Geometric PTASs (polynomial time approximation schemes)

  1. Geometric Embeddings (4 lectures)

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

  1. Scheduling Problems and Resource Augmentation (2 lectures)

Flow-time with and without augmentation

Non-clairvoyant scheduling

  1. Primal-Dual algorithms (2 lectures)

Facility Location and the k-Median Problem

Steiner Network Design (time permitting)

 

---

 

Pre-requisites:

 

MS&E 212 or CS 161 or CS 261 or prior exposure to algorithms, graph theory, NP-completeness, and linear programming.

 

---

 

Workload and grading information:

 

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.

 

---

 

Textbook and reading list:

 

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):

 

  1. A compendium of NP optimization problems – an excellent resource.
  2. G. Nemhauser, L. Wolsey, M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14(1978), 265.294.
  3. David Kempe, Jon Kleinberg, Éva Tardos: Maximizing the Spread of Influence in a Social Network. In Proceedings of KDD 2003, Washington DC.
  4. Energy-efficient Broadcast in Wireless Ad-hoc Networks: Lower bounds and Algorithms. F. Bian, A. Goel, C. Raghavendra, and X. Li. Journal of Interconnection Networks, 3(3-4), September & December 2002, pages 149-166.
  5. A tight bound on approximating arbitrary metrics by tree metrics.  J. Fakcharoenphol , S. Rao, and K. Talwar. ACM STOC 2003: 448-455.
  6. Buy-at-bulk network design. B. Awerbuch and Y. Azar. IEEE FOCS 1997.
  7. Simpler and Better Approximation Algorithms for Network Design. A. Kumar, A. Gupta, T. Roughgarden. ACM STOC 2003.
  8. R. Hassin. Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research, 17(1):36--42, February 1992.
  9. Simultaneous optimization via approximate majorization for concave profits or convex costs. A. Goel and A. Meyerson. To appear in Algorithmica.
  10. The geometry of graphs and some of its algorithmic applications, N. Linial, E. London and Yu. Rabinovich, Combinatorica, 15(1995) 215 – 245.
  11. Euclidean distortion and the sparsest cut.. S. Arora, J. Lee, and A. Naor. To appear in STOC 2005.

 

 

---

 

Handouts:

 

  1. Tell us about yourself. Given 1/6. Due 1/11.
  2. Homework 1. Given 1/18. Due 1/27.
  3. Homeworks 2 & 3 (combined). Given 2/28. Due 3/10. PDF version, in case your browser does not like the html version.

 

---

 

What we will not teach:

 

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.

 

---

 

Announcements:

 

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.

 

---