Title: Primal-dual and Lagrangian relaxation techniques for k-median
|Speaker:||Madison Van Dyk|
|Affiliation:||University of Waterloo|
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.
200 University Avenue West
Waterloo, ON N2L 3G1