Polynomial Time Algorithms for NP-Hard Problems Which Are Optimal or Near-Optimal With Probability One

Abstract

This paper presents 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 packof 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 on the size of the problem instance. Furthermore, we show that each algorithm gives an optimal or near-optimal solution with probability one, as the size of the corresponding problem instance increases.