Spring school

"Mathematical Programming and Design of Approximation Algorithms"
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

and the k-median problem

The traveling salesman problem

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

and the prize-collecting TSP