<p>In the <span class="math-container">$k$</span>-median problem, <span class="math-container">$L$</span> defines as set of feasible facility locations and <span class="math-container">$C$</span> defines a set of client locations in a metric space.</p>
<p>The current best approximation guarantee for the problem is <span class="math-container">$2.675$</span> due to <a href="https://dl.acm.org/doi/10.1145/2981561" rel="noreferrer">Byrka <em>et al.</em></a>  Do we have any better approximation guarantees for the problem when <span class="math-container">$L=C$</span>? If not, is it possible to show that the same <span class="math-container">$(1+\frac{2}{e})$</span> hardness of approximation holds when <span class="math-container">$L = C$</span>?</p>
<hr />
<p>I am aware that the <span class="math-container">$k$</span>-center problem admits a <span class="math-container">$3$</span>-approximation in the general case. And, that it can be improved to <span class="math-container">$2$</span>-approximation when <span class="math-container">$L = C$</span>. Moreover, both these bounds are tight in their respective cases. I am hoping for a similar behavior for the <span class="math-container">$k$</span>-median problem. Any help is appreciated. Thanks.</p>

CC BY-SA 4.0
2022-02-23T01:17:31.520Z
@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.
ErroR
CC BY-SA 4.0
2021-02-25T11:18:38.157Z
Btw, the $k-$center variant when $L\neq C$ necessarily is usually called $k-$supplier problem.
user3508551
CC BY-SA 4.0
2021-02-25T14:59:57.533Z
@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
<clustering><metric-spaces>
Does k-Median problem become any easier when L = C?
Inuyasha Yagami
# Does k-Median problem become any easier when L = C?

(Asked by: username_0 on 2021-02-24)

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.*](https://dl.acm.org/doi/10.1145/2981561) 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.

**Tags:** clustering, metric-spaces
> **Comments:**
> **username_2**: Btw, the $k-$center variant when $L\neq C$ necessarily is usually called $k-$supplier problem.  
> **username_0**: @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.  
> **username_1**: @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.  

---

## 0 answers

