×

The probabilistic analysis of combinatorial optimization algorithms. (English) Zbl 0584.68053

Proc. Int. Congr. Math., Warszawa 1983, Vol. 2, 1601-1609 (1984).
[For the entire collection see Zbl 0553.00001.]
One way to validate or compare imperfect algorithms for NP-hard combinatorial problems is simply to run them on typical instances and see how often they fail. This paper explores a complementary theoretical approach, in which we assume that the problem instances represented to the algorithm are drawn from some natural probability distribution. On this assumption we investigate the probability that the algorithm fails. While probabilistic assumptions are always open to question, the approach seems to have considerable explanatory power, and it certainly provides an interesting new realm for the application and extension of a variety of results in probability theory.
In section 2 we apply the probabilistic approach to the problem of partitioning a given set of numbers into two subsets, A and B, such that the sum of the elements in A is as nearly equal as possible to the sum of the elements in B. Determining an optimal partition is very hard, but we show that a remarkably simple algorithm gives an excellent approximate solution with high probability. Section 3 is concerned with the construction of Hamiltonian circuits, matchings, maximum cliques and minimum colorings in random graphs. The development can be viewed as the extension of the classical Erdős-Rényi theory of random graphs in a highly constructive direction, in which we are concerned not only with the probability that a random graph has a certain property, but also with the probability that an efficient algorithm will succeed in establishing that the property holds. Finally, in sections 4 and 5 we show that certain simple and efficient algorithms have a high probability of producing near-optimal solutions to random instances of the notorious traveling-salesman problem. Section 4 takes up the asymmetric version of the problem, and the Euclidean version is discussed in section 5.

MSC:

68W99 Algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
05C80 Random graphs (graph-theoretic aspects)
90C35 Programming involving graphs or networks

Citations:

Zbl 0553.00001