6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Btw, the $k-$center variant when $L\neq C$ necessarily is usually called $k-$supplier problem. $\endgroup$
    – user3508551
    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$
    – Inuyasha Yagami
    Feb 25, 2021 at 14:59
  • $\begingroup$ @user3508551 Thanks. I did not know that. $\endgroup$
    – Inuyasha Yagami
    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

0

Reset to default

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.