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

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.