On the Euclidean assignment problem
type: Item
instance of: scholarly article
title: On the Euclidean assignment problem
zbMATH Open document ID: 0654.90070
DOI: 10.1016/0377-0427(88)90001-5
author: Franz Rendl
published in: Journal of Computational and Applied Mathematics
publication date: 1988-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4068625
zbMATH Keywords: asymptotic optimality
zbMATH Keywords: bipartite matching
zbMATH Keywords: permutations
zbMATH Keywords: linear time heuristic algorithm
zbMATH Keywords: Euclidean assignment problem
MaRDI profile type: Publication
full work available at URL: 0377-0427(88)90001-5
OpenAlex ID: W2071552074
cites work: On optimal matchings
cites work: An in-core/out-of-core method for solving large scale assignment problems
cites work: A partitioning algorithm for minimum weighted Euclidean matching
cites work: Partitioning heuristics for two geometric maximization problems
cites work: Heuristics for planar minimum‐weight perfect metchings
cites work: Q5519710
cites work: Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
cites work: Euclidean matching problems and the metropolis algorithm
Recommended article: The number of optimal matchings for Euclidean assignment on the line
Recommended article: The Euclidean Matching Problem
Recommended article: The assignment problem revisited
Recommended article: On solving a variation of the assignment problem
Recommended article: Q4840113
Recommended article: Q4209365
Recommended article: The Euclidean k-Supplier Problem
Recommended article: The Euclidean Multifacility Location Problem
Recommended article: Q3147670
description: scientific article; zbMATH DE number 4068625