Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-24T04:21:37.490Z Has data issue: false hasContentIssue false
  • English
  • Français

Stochastic analysis of partitioning algorithms for matching problems

Part of: Limit theorems

Published online by Cambridge University Press:  14 July 2016

Ludger Rüschendorf  and
Gernot Sachs
Ludger Rüschendorf*
Affiliation:
University of Freiburg
Gernot Sachs*
Affiliation:
University of Freiburg
*
∗Postal address: Institut für Mathematische Stochastik, Universität Freiburg, Eckerstr. 1, D-79104 Freiburg, Germany
∗Postal address: Institut für Mathematische Stochastik, Universität Freiburg, Eckerstr. 1, D-79104 Freiburg, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

Partitioning algorithms for the Euclidean matching and for the semi-matching problem in the plane are introduced and analysed. The algorithms are analogues of Karp's well-known dissection algorithm for the travelling salesman problem. The algorithms are proved to run in time nlogn and to approximate the optimal matching in the probabilistic sense. The analysis is based on the techniques developed in Karp (1977) and on the limit theorem of Redmond and Yukich (1993) for quasiadditive functionals.

Keywords

Matching problempartitioning algorithmquasiadditive functional

MSC classification

Primary: 60F99: None of the above, but in this section
Type
Research Papers
Information
Journal of Applied Probability , Volume 37 , Issue 2 , June 2000 , pp. 494 - 503
Copyright
Copyright © by the Applied Probability Trust 2000 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Dyer, M. E., and Frieze, A. M. (1984). A partitioning algorithm for minimum Euclidean matching. Inf. Process. Lett. 18, 59–62.Google Scholar
Halton, J. H., and Terada, R. (1982). A fast algorithm for the Euclidean travelling salesman problem optimal with probability one. SIAM J. Comp. 11, 28–46.Google Scholar
Karp, R. M. (1977). The probabilistic analysis of partitioning algorithms for the travelling salesman problem in the plane. Math. Operat. Res. 2, 209–224.Google Scholar
Karp, R. M., and Steele, J. M. (1985). Probabilistic analysis of heuristics. In The Travelling Salesman Problem, eds Lawler, E. L. et al. John Wiley, New York, pp. 185–205.Google Scholar
Ottmann, T., and Widmayer, P. (1990). Algorithmen und Datenstrukturen. BI-Wiss, Mannheim, Germany.Google Scholar
Papadimitriou, C. H. (1978). The probabilistic analysis of matching heuristics. In Proc. 15th Ann. Conf. Comm. Control Computing. University of Illinois, Urbana, IL, pp. 363–378.Google Scholar
Papadimitriou, C. H., and Steiglitz, K. (1982). Combinatorial Optimization, Algorithms and Complexity. Prentice Hall, New Jersey.Google Scholar
Redmond, C., and Yukich, J. E. (1994). Limit theorems and rates of convergence for Euclidean functionals. Ann. Appl. Prob. 4, 1057–1073.Google Scholar
Rhee, W. S. (1993). A matching problem and subadditive Euclidean functionals. Ann. Appl. Prob. 3, 794–801.Google Scholar
Sachs, G. (1997). Matching Probleme und Approximationsalgorithmen. Diplomarbeit, Universität Freiburg.Google Scholar
Steele, J. M. (1997). Probability theory and combinatorial optimization. CBMS-NSF Regional Conf. Ser. Appl. Math. Society for Industrial and Applied Mathematics, Philadelphia.Google Scholar
Vajda, P. M. (1995). Geometry helps in matching. SIAM J. Comput. 18, 1201–1225.Google Scholar
Yukich, J. E. (1995). Quasi-additive Euclidean functionals. In Discrete Probability and Algorithms, eds Aldous, D. et al. Springer, New York, pp. 149–158.Google Scholar