Tentative Calendar
| Week | Topic | Handouts |
Reading |
| Jan 14 | Administrivia; Review of NP-completeness and polynomial-time
reductions Approximation ratio and complexity classes; Vertex cover |
Problem
Set 1 |
Appendix A |
| Jan 21 |
Vertex cover Constant factor approximation, Layering |
Chapter 1 | |
| Jan 28 |
Set cover: Greedy
algorithm Example applications: Abstracts many resource selection problems |
|
Chapter 2 |
| Feb 4 | Shortest superstring: Constant-factor approximation Example applications: computational biology, data compression |
Problem
Set 2 |
Chapter 7 |
| Feb 11 |
Feedback vertex set: Constant-factor approximation | Chapter 6 |
|
| Feb 18 |
Knapsack & bin-packing: Polynomial-time
approximations schemes Example applications: Packaging, manufacturing, encryption |
|
Chapters 8 and 9 |
| Feb 25 |
Traveling Salesperson problem: Metric and Euclidean
versions Example applications:VLSI design, X-ray crystallography |
Problem Set 3 | Chapters 3 and 11 |
| Mar 3 |
Spring Break | ||
| Mar 10 |
Linear programming: Introduction and the geometry of LP LP-duality: The weak and strong duality theorems |
Problem
Set 4 |
Handout on LP, Chapter 12 |
| Mar 17 |
LP-based algorithms for set
cover Dual-fitting, rounding, and primal-dual methods |
|
Chapters 13-15 |
| Mar 24 | Facility location:
k-center, k-median, and related problems; Combinatorial algorithms for k-center and k-median Example applications: Network design, data clustering |
Chapter 5, handout | |
| Mar 31 |
Facility location:
LP-based algorithms LP-relaxation, randomized rounding, and the primal dual techniques Example applications: Network design, data clustering |
Chapters 24 and 25 | |
| Apr 7 | Hardness
of Approximation The PCP Theorem and its applications Hardness of clique and set cover |
|
Chapter 29 |
| Apr 14 |
Selected
Topics: Online computation The notion of competitive ratio; Paging, the k-server problem Example applications: Load balancing, virtual circuit routing, portfolio allocation Semidefinite programming: An overview, and application to MAX-SAT |
|
Chapter 26 Handout |
| Apr 21 |
Student presentations | |
Note: All handouts are in PDF.