Facility location and $k$-medians are closely related problems in CS. We are given a set of facilities (each with a weight), a set of clients to serve where a facility $i$ can serve a client $j$ with a cost of $c_{ij}$. In $k$-medians problem, the goal is to select a set of $k$ facilities that minimizes the total cost incurred in serving the clients.
Consider the following weighted version of the problem. Select a set of facilities with a total weight of at most $W$ that minimizes the total cost incurred in serving the clients. [I don't think I have ever seen this version, and as far as I understand the known approximation algorithms do not extend to this version --- but I have limited expertise, so could be wrong.]
Any pointers/thoughts are appreciated.
