On the Euclidean assignment problem (Q1108932): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: On optimal matchings / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: An in-core/out-of-core method for solving large scale assignment problems / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A partitioning algorithm for minimum weighted Euclidean matching / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Partitioning heuristics for two geometric maximization problems / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Heuristics for planar minimum‐weight perfect metchings / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q5519710 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Euclidean matching problems and the metropolis algorithm / rank | |||
Normal rank | |||
Latest revision as of 19:00, 18 June 2024
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
