19 maja 2015 10:15
[Seminarium ZOK]. Bartosz Rybicki:An Improved Approximation Algorithm for Knapsack Median Using Sparsification
Wtorek, 10:15-12:00, sala 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.