A partitioning algorithm for minimum weighted Euclidean matching
type: Item
instance of: scholarly article
title: A partitioning algorithm for minimum weighted Euclidean matching
zbMATH Open document ID: 0539.68063
DOI: 10.1016/0020-0190(84)90024-3
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: In this paper an example is given of the following heuristics dealing with problems defined on random sets of points distributed uniformly in the Euclidean unit square in the plane: Partition the unit square in a number of smaller subsquares, each containing (on the average) only a small fraction of the points; solve each of these local subproblems, and try to combine these local solutions by some local patching into a global solution for the original instance of the problem. The analysis of the heuristics establishes in a well defined probabilistic model the probability of the event that the result of the heuristics is not much worse than the optimal solution. A classical example where this heuristics has been applied is \textit{R. M. Karp's} application for the Euclidean traveling salesman problem [Math. Oper. Res. 2, 209-224 (1977; Zbl 0391.90091)]. In the present note the heuristics is applied to the problem of finding a minimal weighted Euclidean matching on a set of 2m points selected at random in the unit square. By dividing the square in \(k^ 2\) subsquares with \(k=O(m^{1/2})\) an algorithm is obtained approximating the optimal matching asymptotically with probability 1, such that its running time with high probability is \(O(m^ 3/k^ 2)\). The running time of an algorithm solving the problem exactly is \(O(n^ 3)\).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 3858438
zbMATH Keywords: probabilistic analysis of algorithms
zbMATH Keywords: minimal weighted Euclidean matching
author: Martin Dyer
author: Alan Frieze
reviewed by: Peter van Emde Boas
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90024-3
OpenAlex ID: W1991462609
Wikidata QID: Q56324183
cites work: Worst case bounds for the Euclidean matching problem
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Paths, Trees, and Flowers
cites work: A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
cites work: Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
cites work: Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching
cites work: On a Greedy Heuristic for Complete Matching
cites work: Subadditive Euclidean functionals and nonlinear growth in geometric probability
cites work: Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
cites work: The Travelling Salesman Problem and Minimum Matching in the Unit Square
DBLP publication ID: journals/ipl/DyerF84
Recommended article: An efficient heuristic algorithm for minimum matching
Recommended article: Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
Recommended article: Partitioning heuristics for two geometric maximization problems
Recommended article: On the weighted Euclidean matching problem in Rd
Recommended article: Q4788073
Recommended article: Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
Recommended article: On the Euclidean assignment problem
Recommended article: Average-case approximation ratio of the 2-opt algorithm for the TSP
Recommended article: Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck
description: scientific article; zbMATH DE number 3858438