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. Feb 25, 2021 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. Feb 25, 2021 at 14:59
• @user3508551 Thanks. I did not know that. Feb 25, 2021 at 15:02
• @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.
– Jut
Feb 23 at 1:17