Partitioning heuristics for two geometric maximization problems (Q800827): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Martin Dyer / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Alan M. Frieze / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Colin J. H. McDiarmid / rank | |||
Normal rank |
Revision as of 19:07, 11 February 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