Fast Algorithms for NP-Hard Problems Which Are Optimal or Near-Optimal with Probability One

Abstract

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.