The time complexity of maximum matching by simulated annealing

ABSTRACT

The random, heuristic search algorithm called simulated annealing is considered for the problem of finding the maximum cardinality matching in a graph. It is shown that neither a basic form of the algorithm, nor any other algorithm in a fairly large related class of algorithms, can find maximum cardinality matchings such that the average time required grows as a polynomial in the number of nodes of the graph. In contrast, it is also shown for arbitrary graphs that a degenerate form of the basic annealing algorithm (obtained by letting “temperature” be a suitably chosen constant) produces matchings with nearly maximum cardinality in polynomial average time.

REFERENCES

• 1: ANILY, S., AND FEDERGRUEN, A. Simulated annealing methods with general acceptance probabilities. J. Appl. Prob. 24 (1987), 657-667.
• 2: CERNY, V. A thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. J. Optim. Theory Appl. 45 (1985), 41-5 I.
• 3: CHOW, Y. S. AND TEICHER, H. Probability Theory: Independence, lnterchangeability, Martingales. Spdnger-Verlag, New York, 1978.
• 4: GELFAND, S. B., AND MITTER, S. K. Analysis of simulated annealing for optimization. In Proceedings of the 24th Conference on Decision and Control. IEEE, New York, 1985, pp. 779-786.
• 5: GREENE, J. W., AND SUPOWIT, g.J. Simulated annealing without rejected moves. IEEE Trans. Comput. Aided Des. 5 (1986), 221-228.
• 6: HAJEK, B. Hitting time and occupation time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14 (1982), 502-525.
• 7: Bruce Hajek, Cooling schedules for optimal annealing, Mathematics of Operations Research, v.13 n.2, p.311-329, May 1988 [doi>10.1287/moor.13.2.311]
• 8: HOPCROFT, J. E., AND KARP, R. M. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2 (1973), 225-231.
• 9: KmKPATRICK, S., GELETT, C. D., AND VECCHI, M. P. Optimization by simulated annealing. Science 220 (1983), 621-630.
• 10: MICALI, S. AND VAZIRANI, V.V. An O(',/i VI ~ I EI ) algorithm for finding maximum matching in general graphs. In Proceedings of the 21 st Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1980, pp. 17-27.
• 11: MITRA, D., ROMEO, F. AND SANGIOVANNI-VINCENTELLI, A. Convergence and finite-time behavior of simulated annealing. Adv. Appl. Probab. 18 (1986), 747-771.
• 12: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 13: VECCHI, M. P. AND KtRKPATRICK, S. Global wiring by simulated annealing. IEEE Trans. Comput. Aided Des. 2 (1983), 215-222.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Performance, Theory