On the Euclidean assignment problem (Q1108932)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the Euclidean assignment problem |
scientific article; zbMATH DE number 4068625
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the Euclidean assignment problem |
scientific article; zbMATH DE number 4068625 |
Statements
On the Euclidean assignment problem (English)
0 references
1988
0 references
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.
0 references
asymptotic optimality
0 references
bipartite matching
0 references
permutations
0 references
linear time heuristic algorithm
0 references
Euclidean assignment problem
0 references
0.8966917
0 references
0 references
0 references
0.8829963
0 references
0.8758513
0 references
0 references
0.8729124
0 references
