<p>The <span class="math-container">$k$</span>-median problem is defined as follows: Given a set <span class="math-container">$C$</span> of clients and a set <span class="math-container">$L$</span> of facility locations defined over a distance metric <span class="math-container">$d$</span>. Open a set <span class="math-container">$F$</span> of <span class="math-container">$k$</span> facility in <span class="math-container">$L$</span> such that the total cost of assigning the clients to their closest facilities is minimized, i.e.,</p>
<p><span class="math-container">$$minimize \quad \Phi(F,C) \equiv \sum_{j = 1}^{|C|} \, \min_{f \in F} \big\{ d(j,f) \big\}$$</span></p>
<p>I have the following variant of this problem. The facility set <span class="math-container">$L$</span> is partitioned into <span class="math-container">$k$</span> subsets: <span class="math-container">$L_1,\dotsc,L_k$</span> and one can open at most one facility in any partition <span class="math-container">$L_i$</span>. Has this variant been studied before? Any help is appreciated. Thanks!</p>

CC BY-SA 4.0
2021-10-18T19:57:21.530Z
This is the special case of the matroid median where the chosen facilities must  be an independent set in a given matroid (on the facilities). Your case is the partition matroid. There is a constant factor approximation for matroid median. See https://dl.acm.org/doi/10.5555/2133036.2133120 and https://arxiv.org/abs/1310.7834
Chandra Chekuri
CC BY-SA 4.0
2021-10-18T20:06:13.917Z
@ChandraChekuri Very helpful! Thanks a lot!
Inuyasha Yagami
<approximation-algorithms><clustering>
k-Median Problem With Restricted Centers
Inuyasha Yagami
# k-Median Problem With Restricted Centers

(Asked by: username_0 on 2021-10-18)

The $k$-median problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the total cost of assigning the clients to their closest facilities is minimized, i.e.,

$$minimize \quad \Phi(F,C) \equiv \sum\_{j = 1}^{|C|} \, \min\_{f \in F} \big\{ d(j,f) \big\}$$

I have the following variant of this problem. The facility set $L$ is partitioned into $k$ subsets: $L\_1,\dotsc,L\_k$ and one can open at most one facility in any partition $L\_i$. Has this variant been studied before? Any help is appreciated. Thanks!

**Tags:** approximation-algorithms, clustering

> **Comments:**
> **username_1**: This is the special case of the matroid median where the chosen facilities must  be an independent set in a given matroid (on the facilities). Your case is the partition matroid. There is a constant factor approximation for matroid median. See https://dl.acm.org/doi/10.5555/2133036.2133120 and https://arxiv.org/abs/1310.7834  
> **username_0**: @ChandraChekuri Very helpful! Thanks a lot!  

---

## 0 answers

