An approximation algorithm for the k-median problem with uniform penalties via pseudo-solution

作者：Wu, Chenchen; Du, Donglei; Xu, Dachuan^*

来源：Theoretical Computer Science, 2018, 749: 80-92.

DOI：10.1016/j.tcs.2018.02.026

• Approximation algorithm
• k-Median problem
• Penalty
• Pseudo-solution

We present a (1 + root 3 + is an element of)-approximation algorithm for the k-median problem with uniform penalties, extending the recent result by Li and Svensson for the classical k-median problem without penalties. One important difference of this work from that of Li and Svensson is a new definition of sparse instance to exploit the combinatorial structure of our problem.

• 出版日期2018-11-21
• 单位北京工业大学; 天津理工大学