| Constrained TSP and Low-Power Computing (1997) | |||||||||||||||
Abstract | |||||||||||||||
| . In the precedence-constrainedtraveling salesmanproblem (PTSP) we are givena partial order on n nodes, each of which is labeled by one of k points in a metric space.We are to find a visit order consistent with the precedenceconstraints that minimizes the total cost of the correspondingpath in the metric space. We give negative results on approximability by relating the problem to the Shortest Common Supersequence problem, helping to explain why there has been very little successin approximation algorithms for this problem. We also give approximation algorithms for a number of special cases, included cases appropriate for a problem in low-power computing; in the process, we show that algorithms for the k-server problem and the traveling salesman problem can be used to derive approximation algorithms for the PTSP. We give tight bounds on the approximation ratios achieved by natural classes of algorithms for this optimization problem (which include algorithms proposed and used in empiri... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||