In the $k$-median problem, $L$ defines as set of feasible facility locations and $C$ defines a set of client locations in a metric space.

The current best approximation guarantee for the problem is $2.675$ due to Byrka et al. Do we have any better approximation guarantees for the problem when $L=C$? If not, is it possible to show that the same $(1+\frac{2}{e})$ hardness of approximation holds when $L = C$?

I am aware that the $k$-center problem admits a $3$-approximation in the general case. And, that it can be improved to $2$-approximation when $L = C$. Moreover, both these bounds are tight in their respective cases. I am hoping for a similar behavior for the $k$-median problem. Any help is appreciated. Thanks.

  • 1
    $\begingroup$ Btw, the $k-$center variant when $L\neq C$ necessarily is usually called $k-$supplier problem. $\endgroup$ Feb 25, 2021 at 11:18
  • $\begingroup$ @ChandraChekuri I was thinking along the same lines. However, this idea will not work. The overall k-median cost would be dominated by the newly added clients that are present at the locations where a facility is not opened. The cost due to original clients would become negligle comparison to them. Therefore, this reduction does not create a gap between soundness and completeness cases. $\endgroup$ Feb 25, 2021 at 14:59
  • $\begingroup$ @user3508551 Thanks. I did not know that. $\endgroup$ Feb 25, 2021 at 15:02
  • $\begingroup$ @InuyashaYagami Can I ask a question about k-median in plane? My questions is, suppose we run PTAS algorithm for k-median and the divide the plane into a grid that each cell form a rectangle. Now, if we consider each rectangle as a cluster, can we say this give us a constant approximation factor for k-median in plane? My problem is, I want, each cluster of k-median in plane have a rectangle shape and I try to make each cluster to have a rectangular shape. $\endgroup$
    – Jut
    Feb 23 at 1:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.