Fast Algorithms for NP-Hard Problems Which Are Optimal or Near-Optimal with Probability One
File(s)
Date
1979Author
Terada, Routo
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
We present fast algorithms for six NP-hard problems. These algorithms are shown to be optimal or near-optimal with probability one (i.e., almost surely).
First we design an algorithm for the Euclidean traveling salesman problem in any k-dimensional Lebesgue set E of zero-volume 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 NP-hard 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 k-dimensional 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 near-optimal solution with probability one, as the size of the corresponding probletn instance increases.
Permanent Link
http://digital.library.wisc.edu/1793/58154Citation
TR356