Combinatorial Optimization Reading Group- Sharat Imbrahimpur

Friday, November 2, 2018 1:00 pm - 1:00 pm EDT (GMT -04:00)

Title: Approximating k-Median via Pseudo-Approximation

Speaker: Sharat Ibrahimpur
Affiliation: University of Waterloo
Room: MC 5479

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.