An Improved Approximation Algorithm for Knapsack Median Using Sparsification

作者：Byrka Jaroslaw; Pensyl Thomas; Rybicki Bartosz; Spoerhase Joachim; Srinivasan Aravind^*; Khoa Trinh

来源：Algorithmica, 2018, 80(4): 1093-1114.

DOI：10.1007/s00453-017-0294-4

• Approximation algorithm
• Combinatorial optimization
• Randomized algorithm
• Facility-location problems

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 3.05 approximation with small budget violation.

• 出版日期2018-4