2
$\begingroup$

I have a problem that's been bugging me, but I'm not sure what algorithm can solve it.

Alice has medicine that she needs to use as quickly as possible in case of an allergy attack. She wants to distribute $k$ number of medicines in caches throughout her house, but doesn't know what is the ideal distribution such that at any room (or node) in the house she would travel the least amount of distance.

For simplicity, we map her house into an undirected graph where the edges represent distance to travel from one node (representing a room) to another node. The nodes and edges cannot be altered, and are static.

For $0 < k < |V|$, what algorithm can determine the ideal placement of medicines such that the Alice travels least amount of distance possible from any room (node) as starting point?

$\endgroup$
2
$\begingroup$

These kinds of problems are known as clustering problems. Given an undirected graph $G$, the distance between any two nodes can be defined as the shortest path length between the two nodes. Now, note that the shortest path distances form a metric space.

In the clustering problem, each node represents a client. And, the task is to open $k$ facilities (medicines in your case) at some nodes in the graph such that the transportation cost of all the clients to their closest facility is minimized. There are many ways to quantify the clustering cost, such as $k$-center, $k$-median, and $k$-means objectives. All these problems are $\mathsf{NP}$-hard.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.