# k-Median Problem With Restricted Centers

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!

• 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 dl.acm.org/doi/10.5555/2133036.2133120 and arxiv.org/abs/1310.7834 Oct 18 at 19:57
• @ChandraChekuri Very helpful! Thanks a lot! Oct 18 at 20:06