1
$\begingroup$

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.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.