A partitioning algorithm for minimum weighted Euclidean matching
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)\).
- An efficient heuristic algorithm for minimum matching
- Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
- Partitioning heuristics for two geometric maximization problems
- On the weighted Euclidean matching problem in Rd
- scientific article; zbMATH DE number 1855663
- Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
- On the Euclidean assignment problem
- Average-case approximation ratio of the 2-opt algorithm for the TSP
- Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck
- A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
- Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
- Maximum matching and a polyhedron with 0,1-vertices
- On a Greedy Heuristic for Complete Matching
- Paths, Trees, and Flowers
- Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- The Travelling Salesman Problem and Minimum Matching in the Unit Square
- Worst case bounds for the Euclidean matching problem
- A lower bound to the complexity of Euclidean and rectilinear matching algorithms
- On the Euclidean assignment problem
- Quantizers ad the worst case Euclidean traveling salesman problem
- Heuristic methods and applications: A categorized survey
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- Minimum-error classes for matching parts
- scientific article; zbMATH DE number 992001 (Why is no real title available?)
- An efficient heuristic algorithm for minimum matching
- A survey of heuristics for the weighted matching problem
- Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
- A Monte Carlo solution to the minimal Euclidean matching
- scientific article; zbMATH DE number 1202983 (Why is no real title available?)
- On the weighted Euclidean matching problem in Rd
- Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
- Randomized algorithms for the on-line minimum matching problem on euclidean space
- Equitable connected partition and structural parameters revisited: N-fold beats Lenstra
- Partitioning heuristics for two geometric maximization problems
This page was built for publication: A partitioning algorithm for minimum weighted Euclidean matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794175)
