In the {\em precedence-constrained traveling salesman problem (PTSP)}
we are given a 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 precedence constraints that minimizes the total
cost of the corresponding path 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 success in 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 empirical studies of this problem).  We briefly summarize
results of experiments with several algorithms on a standard set of
compiler benchmarks, comparing several known and new algorithms.