Combinatorial Optimization Reading Group- Sharat Imbrahimpur

Title: Approximating k-Median via Pseudo-Approximation

Abstract: In the last two talks we saw two approaches for approximating k-median. The first approach was to use primal-dual method to approximate uncapacitated facility location and then extend this algorithm, at a loss of factor of 2, to k-median in a blackbox fashion by using the Lagrangian relaxation technique. In the second approach we saw that local search with p swaps gives a 3+2/p-approximation. For more than a decade beating the 3-approximation guarantee for k-median was considered an important open problem. In this talk I will present a 2.74-approximation algorithm for k-median based on the work of Shi Li and Ola Svensson by the same title.