Combinatorial Optimization

Title: Primal-dual and Lagrangian relaxation techniques for k-median

Abstract: We will develop primal-dual algorithms to obtain constant-factor approximations for the uncapacitated facility location problem. We will then show how Lagrangian relaxation can be used to extend these techniques for the k-median problem. This talk is based on the relevant sections of The Design of Approximation Algorithms by Shmoys and Williamson, and Approximation Algorithms for Facility Location Problems by Jens Vygen.