Partitioning heuristics for two geometric maximization problems (Q800827)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3878681
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Partitioning heuristics for two geometric maximization problems |
scientific article; zbMATH DE number 3878681 |
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
0 references
0 references
0.860322892665863
0 references
0.774083137512207
0 references
0.7712091207504272
0 references
0.7706406712532043
0 references
0.7706406712532043
0 references
