Partitioning heuristics for two geometric maximization problems (Q800827): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q56324191, #quickstatements; #temporary_batch_1705082136280 |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 11:05, 30 January 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Partitioning heuristics for two geometric maximization problems |
scientific article |
Statements
Partitioning heuristics for two geometric maximization problems (English)
0 references
1984
0 references
Given n points randomly selected from a uniform distribution on the unit square, we describe linear-time partitioning heuristics which will construct a matching or a tour of these points. We show that the heuristics closely approximate the optimum values as \(n\to \infty\). Hence we show that the asymptotic values of the maximum matching and tour are about 0.3826n and twice this value respectively.
0 references
geometric maximization
0 references
linear-time partitioning heuristics
0 references
