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!

  • 5
    $\begingroup$ 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 $\endgroup$ Oct 18 at 19:57
  • $\begingroup$ @ChandraChekuri Very helpful! Thanks a lot! $\endgroup$ Oct 18 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.