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?
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?
This is an assignment problem which can, for example, be solved by the Hungarian algorithm or by expressing it as linear program. Note that you can adapt your problem to the definition by padding the set of agents with $N-m$ dummy agents which have travel cost $0$ to all nodes.
how about creating tuples of all M agents with N points, sorting them by distance and then greedily picking the first M. this is basically what kruskal does. we could modulate this as a graph where we have a root noe connected to all agents(with edge weight 0) then create all edges from agents to points with the distance as weight, the mst should be the answer we are looking for. is this correct?