In this paper, we combine the techniques of approximation, parallelism, and randomization to solve the traveling salesman problem, one of the most celebrated problems in computer science. We show that there is an EREW PRAM algorithmA1such thatA1(l) ≤ 2 OPT(l) for all TSP instancesl, whereA1(l) is the length of the tour produced byA1, and OPT(l) is the length of an optimum tour. The algorithm has time complexityO(log2 n), and usesO(n2) processors. There is a similar CREW PRAM algorithmA2that usesO(n2/log2 n) processors. Furthermore, there is a Monte Carlo CREW PRAM algorithmA3which, for all TSP instancesl, finds a traveling salesman lour such thatA3(l) ≤ 1.5OPT(l) with probability at least 1 − (1/2k), wherekis any large integer. The randomized algorithm has time complexityO(log2 n), and usesO(n5.5L) processors, whereLis the length of the interval which contains all distances inl. We also show that there is a Las Vegas CREW PRAM algorithmA4which, for all TSP instancesl, produces a traveling salesman tour such thatA4(l) ≤ 1.5 OPT(l), with expected time complexityO(log2 n), and usingO(n5.5L) processors. Therefore, it is possible to accurately solve the TSP very fast with high probability by using a reasonable amount of resources.