SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS
Title:
SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS
Author:
Li, Keqin
Appeared in:
International journal of parallel, emergent and distributed systems
Paging:
Volume 10 (1997) nr. 3-4 pages 271-281
Year:
1997
Contents:
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 algorithm A1 such that A1(l) ≤ 2 OPT(l) for all TSP instances l, where A1(l) is the length of the tour produced by A1, and OPT(l) is the length of an optimum tour. The algorithm has time complexity O(log2 n), and uses O(n2) processors. There is a similar CREW PRAM algorithm A2 that uses O(n2/log2 n) processors. Furthermore, there is a Monte Carlo CREW PRAM algorithm A3 which, for all TSP instances l, finds a traveling salesman lour such that A3(l) ≤ 1.5OPT(l) with probability at least 1 - (1/2k), where k is any large integer. The randomized algorithm has time complexity O(log2 n), and uses O(n5.5L) processors, where L is the length of the interval which contains all distances in l. We also show that there is a Las Vegas CREW PRAM algorithm A4 which, for all TSP instances l, produces a traveling salesman tour such that A4(l) ≤ 1.5 OPT(l), with expected time complexity O(log2 n), and using O(n5.5L) processors. Therefore, it is possible to accurately solve the TSP very fast with high probability by using a reasonable amount of resources.
Journal description