On the Euclidean assignment problem

DOI10.1016/0377-0427(88)90001-5MaRDI QIDQ1108932zbMATH OpenOpenAlexFDO

Authors Franz Rendl

Publication date 1988

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-0427(88)90001-5

zbMATH Keywords

asymptotic optimalitybipartite matchingEuclidean assignment problemlinear time heuristic algorithmpermutations

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Review text

A linear time heuristic algorithm for the maximization case of the Euclidean assignment problem is described in the paper. It has an absolute error of order \(O(n^{5/6})\). If the points are uniformly distributed in the unit square the algorithm is asymptotically optimal.

Recommendations

• The number of optimal matchings for Euclidean assignment on the line
• The Euclidean Matching Problem
• The assignment problem revisited
• On solving a variation of the assignment problem
• scientific article; zbMATH DE number 776093
• scientific article; zbMATH DE number 1202983
• The Euclidean k-supplier problem
• The Euclidean \(k\)-supplier problem
• The Euclidean Multifacility Location Problem
• scientific article; zbMATH DE number 1803767

Cites work

• A partitioning algorithm for minimum weighted Euclidean matching
• An in-core/out-of-core method for solving large scale assignment problems
• Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
• Euclidean matching problems and the metropolis algorithm
• Heuristics for planar minimum‐weight perfect metchings
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• On optimal matchings
• Partitioning heuristics for two geometric maximization problems

Cited in

(9)

• On the Euclidean two paths problem
• The Euclidean \(k\)-supplier problem in \(\mathbb R^2\)
• Fiber-to-object assignment heuristics
• The Euclidean Matching Problem
• scientific article; zbMATH DE number 3900504 (Why is no real title available?)
• On Assignment Problems Related to Gromov–Wasserstein Distances on the Real Line
• Euclidean maximum matchings in the plane -- local to global
• A partitioning algorithm for minimum weighted Euclidean matching
• Euclidean maximum matchings in the plane -- local to global

This page was built for publication: On the Euclidean assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108932)