4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ it might be a good question..if we could understand what the question is $\endgroup$ – Sasho Nikolov Jul 15 '12 at 18:54
  • 4
    $\begingroup$ My interpretation of the problem: You have to move $m$ agents so that each agent uniquely occupies one of $N$ fixed points, and you want to find the mapping that minimizes total distance. This can be solved as a min-cost flow problem. $\endgroup$ – Aaron Jul 15 '12 at 20:11
  • 7
    $\begingroup$ Specifically, it's a min-weight bipartite matching problem. $\endgroup$ – JeffE Jul 15 '12 at 22:46
  • $\begingroup$ I'm having difficulty understanding what quantity you want to minimize. What do you mean by "total distance covered by the agents"? Is there some definition of when a point is covered by an agent, or something? $\endgroup$ – D.W. Oct 3 '14 at 0:37
4
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ A really interesting issue here is the first question made by Rob Simmons: How could we develop a distributed algorithm which solves the problem? $\endgroup$ – d. th. man Jul 18 '12 at 9:21
  • $\begingroup$ @d.th.man Practically, we can't, if you take a "distributed algorithm" to mean that each agent decides where to go, then observes where the others go and possibly changes its destination. If any of them starts moving and doesn't target to the place where the optimal solution would take him, a distributed algorithm cannot be optimal anymore. $\endgroup$ – gnasher729 Dec 30 '18 at 20:38
4
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If @Raphael's answer, which does not depend on greedy algorithms, is correct, this answer is unlikely to be correct. $\endgroup$ – John L. Dec 30 '18 at 11:39
  • $\begingroup$ but kruskal is proved to be right. and what i am offering is creating an mst. the mst kruskal picks is basically the best option for each robot given the constraints. could you elaborate a bit why you think this is incorrect? $\endgroup$ – Hanani Corney Dec 30 '18 at 12:13
  • $\begingroup$ Two agent A1 and A2. Two point P1 and P2. d(A1, P1)=1, d(A1, p2)=2, d(A2,p1)=2, d(A2,p2)=10. Greedy choice will not work. $\endgroup$ – John L. Dec 30 '18 at 12:22
  • $\begingroup$ You are welcome. $\endgroup$ – John L. Dec 30 '18 at 12:46
  • $\begingroup$ @Apass.Jack Your counterexample violates the triangular equation. Would be interesting to know what's the worst case for the greedy algorithm for n targets, m agents, and all distances being euclidean distances. You could add a second phase where two agents swap destinations if it leads to savings. $\endgroup$ – gnasher729 Dec 30 '18 at 20:41

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.