Fast Algorithms for NPHard Problems Which Are Optimal or NearOptimal with Probability One
Routo Terada
1979
We present fast algorithms for six NPhard problems. These algorithms are shown to be optimal or nearoptimal with probability one (i.e., almost surely). First we design an algorithm for the Euclidean traveling salesman problem in any kdimensional Lebesgue set E of zerovolume boundary. For n points independently, uniformly distributed in E, we show that, in probability, the time taken by the algorithm is of order less than n o(n), as n > a, for any choice of an increasing function (however slow its rate of increase). The r esulting solution will, with probability one, be asymptotic, as n > m, to the optimal solution. In addition, by applying a uniform method, we design algorithms for five NPhard problems: the vertex set cover of an undirected graph, the set cover of a collection of sets, the clique of an undirected graph, the set pack of a collection of sets, and the kdimensional matching of an undirected graph. Each algorithm has its worst case running time bounded by a polynomial or a function slightly greater than a polynomial on the size of the problem in stance. Furthermore, we show, as corollaries of main theorems, that each algorithm gives an optimal or nearoptimal solution with probability one, as the size of the corresponding probletn instance increases.
Download this report (PDF)
Return to tech report index
