On the Euclidean assignment problem (Q1108932)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the Euclidean assignment problem |
scientific article |
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
