Nonpreemptive Ensemble Motion Planning on a Tree

Consider the problem of transporting a set of objects between the vertices of a tree by a vehicle that travels along the edges of the tree. The vehicle can carry only one object at a time, and it starts and finishes at the same vertex of the tree. It is shown that if each object must be carried directly from its initial vertex to its destination, then finding a minimum cost transportation is NP-hard. Several fast approximation algorithms are presented for this problem. The fastest runs in O(k + n) time and generates a transportation of cost at most 3/2 times the cost of an optimal transportation, where n is the number of vertices in the tree, k is the number of objects to be moved. Another runs in O(k + nlogbeta(n,q)) time, and generates a transportation of cost at most 5/4 times the cost of an optimal transportation, where q is less than or equal to min{k,n} is the number of nontrivial connected components in a related directed graph. * Has since been revised by author. Contact him via "gnf at cs.purdue.edu" for a current copy.

ICSI Technical Report TR-89-012

Technical Report