Instructor: Viswanath Nagarajan (IOE 2713)
Term: Winter 2017
Office hours: Mondays 3:00 — 4:30PM or by appointment.
Lectures: Mondays and Wednesdays, 1:30 — 3:00PM, EECS Room 1005
Description: Many optimization problems are NP-hard, which means that one cannot expect any algorithm to be both efficient and optimal. These “hard” optimization problems arise in various applications such as network design, scheduling, transportation, supply-chain and robotics. The most common practical approach to such problems is via heuristics, which are algorithms that run fast but settle for sub-optimal solutions. Approximation algorithms provide a mathematical foundation for heuristics by quantifying their gap from optimality. This course is on designing approximation algorithms for a wide range of NP-hard optimization problems. The primary focus is on general techniques, which includes greedy algorithms, local search, dynamic programming, rounding linear/semidefinite programs, primal-dual algorithms and Lagrangian relaxation. These techniques will be demonstrated in the context of basic combinatorial optimization problems such as facility location, scheduling, bin packing, set cover, Steiner network, maximum cut and traveling salesman. Additional topics include hardness of approximation and use of non-linear relaxations. All the topics will involve mathematical proofs. Some topics may change depending on the pace of the course.
Textbook: Design of approximation algorithms, by David Williamson and David Shmoys.
We will also use some material from the book Approximation algorithms, by Vijay Vazirani. Online lecture notes from similar courses at other universities (eg. CMU, Cornell, UIUC) are also good resources.
Prerequisite: No formal requirement. Background in linear programming and optimization will be helpful, though the instructor will summarize relevant concepts. Mathematical maturity (ability to understand and write proofs) will be needed.
| Date | Topic | Reference | Scribe |
| 1/4 | course introduction, MST (greedy) | Ch 1.1 [WS] | Cheng Sun (1) |
| 1/9 | TSP, k-center (greedy) | Ch 2.2, 2.4 [WS] | Karmel Shehadeh (2) |
| 1/11 | k-center hardness, max coverage (greedy) | Ch 2.2, 2.5 [WS] | Sentao Miao (3) |
| 1/18 | set cover (greedy), max matching (local search) | Ch 1.6 [WS] | Qi Luo (4) |
| 1/23 | min degree spanning tree (local search) | Ch 2.6 [WS] | Qingya Liu (5) |
| 1/25 | k-median (local search) | Ch 9.2 [WS] | Haofan Zhang (6) |
| 1/30 | max-cut (local search); independent set on trees, longest path on DAGs, knapsack (DP) | Ch 3.1 [WS] | Gian-Gabriel Garcia (7) |
| 2/1 | knapsack, bin packing (DP) | Ch 3.1, 3.2 [WS] | Fatimeh Navidi (8) |
| 2/6-2/8 | Euclidean TSP (DP) | Ch 10.1 [WS]
| Miao Yu (9) |
| 2/13 | Metric facility location (LP rounding) | Ch 4.5 [WS]
| Runsheng Du (10) |
| 2/15 | Min-cut, Non-metric facility location (random LP rounding) | Ch 1.7 [WS] | Kevin Sung (11) |
| 2/20 | Chernoff bounds, multicommodity routing (random LP rounding) | Ch 5.10-11 [WS] | Biaoshuai Tao (12) |
| 2/22 | Group Steiner tree (random LP rounding) | Paper | Parker Koch (13) |
| 3/6- 3/8 | Tree embedding, multicut, balanced separator (LP rounding) | Ch 8.5, 8.3, 8.4 [WS] | Xiangkun Shen (14, 15) |
| 3/13 | Prize-collecting Steiner tree (exp-size LPs) | Ch 4.3, 4,4, 5.7 [WS] | Yutong Wang (16) |
| 3/15 | Generalized assignment (iterative LP) | Ch 3.2 in book [LRS] | Hao Yuan (17) |
| 3/20 | Degree-bounded MST (iterative LP) | Ch 4.1 in book [LRS] | Chengyu Dai (18) |
| 3/22 | Degree-bounded MST (iterative LP) | Ch 4.4 in book [LRS] | Mayank Agrawal (19) |
| 3/27 | k-Set cover, Steiner forest (primal-dual LP) | Ch 7.1, 7.4 [WS] | Yuchen Jiang (20) |
| 3/29 | Prize-collecting Steiner tree (primal-dual LP) | Ch 14.1 [WS] | Yanzhe Lei (21) |
| 4/3 | k-MST (Lagragian relaxation) | Paper 1, 2 | Cupjin Huang (22) |
| 4/5 | Max-cut (SDP rounding) | Ch 6.1, 6.2 [WS] | Cheng Sun (23) |
| 4/10 4/12 4/17 | Student project presentations |