[Solved]: Assign m agents to N points by minimizing the total distance

Problem Detail: 

Suppose we have $N$ fixed points (set $S$ with $|S|=N$) on the plane and $m$ agents with fixed, known initial positions ($m<N$) outside $S$. We should transfer the agents so that in our final configuration they are all positioned to different points of $S$. How could we achieve it by minimizing the total distance covered by the agents?

Asked By : d. th. man

Answered By : Rob Simmons

My understanding of this question is that you have a two lists of $n$ two-dimensional coordinates. The first list represents the position of a bunch of agents (robots, maybe, or police cars). The second list represents where those agents need to go (which places need to have police cars dispatched to them), and may be longer than the first list.

It is always possible to minimize the sum distance traveled by all agents, if that's what you're worried about: there are $!n$ ways we could dispatch the robots to new positions, we can enumerate all of them, calculate the distance the agents have to travel, and pick the one that has the least distance. As written, "enumerate all the possibilities" I think counts as an answer to your question, though it's probably not the one you wanted.

There are a couple of more precise questions, all or none of which might be interesting and/or research-level. (I'm not a Theory A person...)

• Is a solution possible if each agent (robot/police officer) has to make a decision independently, or has a limited ability to coordinate with other agents?

• How quickly could the central dispatcher come up with a plan to dispatch everyone most efficiently?

  Aaron Roth observes in the comments that this can be solved as a min-cost flow problem. I think that solution looks like this (hopefully I won't make a total fool of myself here): each agent is a source vertex and each dispatch target is an intermediate vertex. There is a capacity-1 edge from each source to a vertex representing the dispatch target, and the cost along that edge is proportional to the distance between the agent's initial position and the dispatch target. There is also a capacity-1, cost-0 edge from each dispatch target vertex to the sink.

• How quickly could the central dispatcher come up with a plan to dispatch everyone that is some multiple of the most efficient solution?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2771