"Mathematical Programming and Design of Approximation Algorithms"
by
David Shmoys and
David Williamson
The material for the course will be drawn from our recent book The Design of Approximation Algorithms (DAA), and be augmented by several recent papers. We list below the topics of the course, the associated sections of the book and the related additional papers (though the papers cited in these book sections might also be covered more completely than in the text). The list below is probably somewhat too ambitious for the allotted time.
The uncapacitated facility location problem
- Deterministic (DAA 4.5) and randomized rounding (DAA 5.8, DAA 12.1), primal-dual method (DAA 7.6) and local search (DAA 9.1)
and the k-median problem
- Lagrangean relaxation (DAA 7.7) and local search (DAA 9.2)
The traveling salesman problem
- Greedy algorithms (DAA 2.4)
- L. A. Wolsey, Heuristic analysis, linear programming and branch and bound, In Combinatorial Optimization II, volume 13, Mathematical Programming Studies, pages 121-134. Springer, 1980
- T. Mömke and O. Svensson, Approximating graphic TSP by matchings, Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 560-569, 2011
- M. Mucha, 13/9-approximation for the graphic TSP, to appear in Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), 2012
- H.-C. An, R. Kleinberg, and D. Shmoys, Improving Christofides’ Algorithm for the s-t path TSP, to appear in Proceedings of the 44th Annual ACM Symposium on Theory of Computing
- F. Schalekamp, D. Williamson, A. van Zuylen, A proof of the Boyd-Carr conjecture, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1477-1486, 2012
The Steiner tree problem (primal-dual method, DAA 7.4) and the generalized Steiner tree problem (randomized rounding, DAA 12.3)
The bounded-degree minimum spanning tree problem (deterministic rounding, DAA 11.2)
The minimum-cost knapsack problem (primal-dual method, DAA 7.5)
The prize-collecting Steiner tree problem
- Deterministic rounding (DAA 4.4), randomized rounding (DAA 5.7) and primal-dual method (DAA 14.1)
and the prize-collecting TSP