DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016 · 18 citations · 8 references
ComputingAutonomous SystemsDistributed SystemsMobile SystemsMulti-robot SystemsCollective CommunicationCommunication NetworksDistributed ComputingDistributed CoordinationNetwork OptimizationDelivery ProblemEnergy ConsumptionEnergy-efficient DeliveryNetwork Energy OptimizationSource-target MappingWeighted Graph Representations
We consider the problem of delivering $m$ messages between specified source-target pairs in a weighted undirected graph, by $k$ mobile agents initially located at distinct nodes of the graph. Each agent consumes energy proportional to the distance it travels in the graph and we are interested in optimizing the total energy consumption for the team of agents. Unlike previous related work, we consider heterogeneous agents with different rates of energy consumption (weights~$w_i$). To solve the delivery problem, agents face three major challenges: \emph{Collaboration} (how to work together on each message), \emph{Planning} (which route to take) and \emph{Coordination} (how to assign agents to messages). We first show that the delivery problem can be 2-approximated \emph{without} collaborating and that this is best possible, i.e., we show that the \emph{benefit of collaboration} is 2 in general. We also show that the benefit of collaboration for a single message is~$1/\ln 2 \approx 1.44$. Planning turns out to be \NP-hard to approximate even for a single agent, but can be 2-approximated in polynomial time if agents have unit capacities and do not collaborate. We further show that coordination is \NP-hard even for agents with unit capacity, but can be efficiently solved exactly if they have uniform weights. Finally, we give a polynomial-time $(4\max\tfrac{w_i}{w_j})$-approximation for message delivery with unit capacities.
8
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations
Robert W. Floyd · Communications of the ACM · 1962 · 4K citations · Full text
The Traveling salesman problem: a computational study
Choice Reviews Online · 2007 · 1.8K citations
Matching, Euler tours and the Chinese postman
Jack Edmonds, Ellis L. Johnson · Mathematical Programming · 1973 · 987 citations