Time and location: Tuesday/Thursday 12:05PM - 1:20PM, 341 Deike
Instructor:
Sofya Raskhodnikova
Office hours: Tuesdays, 1:30PM-2:30PM, IST 343F
CSE 565; STAT 318 or MATH 318 (specifically, familiarity with algorithms for network flow, linear programming, and discrete probability; comfort with mathematical proofs)
This course will cover the design and analysis of approximation algorithms for discrete optimization problems. Many problems in computer science and operations research can be modeled as discrete optimization problems, including packing, scheduling, facility location, internet routing, advertising, and network design. Most of these problems are NP-hard, and thus have no efficient exact algorithms unless P=NP. This course will focus on approximation algorithms: efficient algorithms that find provably near-optimal solutions. It will be organized around algorithmic techniques used for designing approximation algorithms, including greedy, local search, dynamic programming, deterministic and randomized rounding of linear and semidefininite programs, primal-dual, and metric embedding.
Primary: The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys, Cambridge University Press, New York, NY, USA, 2011.
Also: Approximation Algorithms, by Vijay V. Vazirani, Springer-Verlag, Berlin, 2001.
Students will be evaluated based on class participation (5%), solutions to homework assignments (45%), a midterm (20%) and a take-home final (30%).
| Date | Syllabus | Reading (reading in advance in bold) | Handouts/Homework |
|---|---|---|---|
| Tu, Jan 10 | Introduction. The Set Cover Problem: linear programming, deterministic rounding. | WS, Chap. 1.1-1.3 | General Information, Collaboration Policy |
| Th, Jan 12 | Set Cover: exploiting a dual solution, primal-dual, greedy. | WS, Chap. 1.4-1.6 | HW1 (due Wednesday): WS 1.5 |
| Tu, Jan 17 | Set Cover: greedy, randomized rounding. | WS, Chap. 1.6-1.7 | |
| Th, Jan 19 | Greedy algorithms and local search: scheduling with deadlines, k-Center. | WS, Chap. 2.1-2.2 | HW2 (due Wednesday): WS 1.1a, 2.1a |
| Tu, Jan 24 | Scheduling on parallel machines, Traveling Salesman. | WS, Chap. 2.3-2.4 | |
| Th, Jan 26 | Lecture by Nithin Varma: Greedy algorithms and local search: float in bank accounts, min-degree spanning trees. | WS, Chap. 2.5-2.6 | |
| Tu, Jan 31 | Lecture by Jalaj Upadhyay: Finish min-degree spanning trees. | WS, Chap. 2.6 | |
| Th, Feb 2 | Edge coloring. Rounding data and dynamic programming: knapsack. | WS, Chap. 2.7-3.1 | HW3 (due Wednesday): WS 3.2 |
| Tu, Feb 7 | Rounding data and dynamic programming: knapsack, scheduling jobs on identical machines | WS, Chap. 3.1-3.2 | |
| Th, Feb 9 | Rounding data and dynamic programming: scheduling jobs on identical machines, bin packing. | WS, Chap. 3.2-3.3 | HW4 (due Wednesday): WS 3.7 |
| Tu, Feb 14 | Rounding data and dynamic programming: bin packing. Deterministic rounding of LPs: minimizing the sum of completion times | WS, Chap. 3.3-4.1 | |
| Th, Feb 16 | Deterministic rounding of LPs:minimizing the weighted sum of competion times, separation oracles | WS, Chap. 4.2-4.3 | HW5 (due Wednesday): WS 4.3 |
| Tu, Feb 21 | Prize-collecting Steiner tree | WS, Chap. 4.4 | |
| Th, Feb 23 | Uncapacitated facility location | WS, Chap. 4.5 | HW6 (due Wednesday): WS 4.6(a) |
| Tu, Feb 28 | Bin packing | WS, Chap. 4.6 | |
| Th, Mar 2 | Sampling and derandomization, MAX-SAT | WS, Chap. 5.1-5.3 | HW7 (due Wednesday after Spring break): WS 5.1 |
| March 4-12 | Spring Break | ||
| Tu, Mar 14 | Snow day: classes canceled | ||
| Th, Mar 16 | Randomized rounding, the better of two solutions, Nonlinear randomized rounding | WS, Chap. 5.4-5.6 | HW8 (due Wednesday): WS 5.6b |
| Tu, Mar 21 | Prize-Collecting Steiner Tree | WS, Chap. 5.7 | |
| Th, Mar 23 | Uncapacitated Facility Location | WS, Chap. 5.8 | HW9 (due Wednesday): WS 5.2b |
| Tu, Mar 28 | Lecture by Nithin Varma: Scheduling a Single Machine | WS, Chap. 5.9 | |
| Th, Mar 30 | Useful probabilistic inequalities. Integer Multicommodity Flow. | WS, Chap. 5.10-5.11 | HW10 (due Wednesday) |
| Last week of classes | Take-home final exam | ||