May 19, 2015, 10:15 a.m.
[COG seminar]. Bartosz Rybicki:An Improved Approximation Algorithm for Knapsack Median Using Sparsification
Tuesday 10:15-12:00, room 310.
Abstract. 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. We also give a 2.96 approximation with small budget violation.
Joint work with Jaroslaw Byrka, Thomas Pensyl, Joachim Spoerhase, Aravind Srinivasan, and Khoa Trinh.