# Does k-Median problem become any easier when L = C?

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.

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