CATS-Nov-6-2015
Title[edit]
An Improved Approximation Algorithm for Knapsack Median
Speaker[edit]
Khoa Trinhh
Abstract[edit]
$k$-median problem is classic facility-location problem in which we are given a set of facilities $F$, a set of clients $C$, and a symmetric distance metric on $F \cup C$. The goal is to open at most $k$ facilities so that the total connection cost from all clients to the nearest open facility is minimized. The current best known approximation ratio for this problem is (2.675+\epsilon) by Byrka et. al. 2015.
Knapsack median is a generalization of the classic $k$-median problem in which we replace the cardinality constraint with a knapsack constraint. It is currently known to be 32-approximable. We improve on the best known algorithms in several ways, including adding randomization and applying sparsification as a preprocessing step. The latter improvement produces the first LP for this problem with bounded integrality gap. The new algorithm obtains an approximation factor of 17.46. I will discuss the technique used to overcome the unbounded integrality gap of this problem as well as the high-level ideas of the new 17.46-approximation algorithm.
This is joint work with Byrka, Pensyl, Rybicki, Srinivasan, and Spoerhase.
