Euclidean semi-matchings of random samples (Q1184341)
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 34342
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Euclidean semi-matchings of random samples |
scientific article; zbMATH DE number 34342 |
Statements
Euclidean semi-matchings of random samples (English)
0 references
28 June 1992
0 references
The linear relaxation of a minimal matching problem is investigated from a probabilistic point of view. The vertices of the graphs considered here are points chosen at random in an Euclidean space, and the edge weights are the distances between points of the space. The main result is the asymptotic behavior of the length of a minimal matching when the points of the space are independent random variables with uniform distribution on \([0,1]^ d\). This result is then extended to the more general case of distributions with compact support and absolutely continuous part.
0 references
linear relaxation
0 references
minimal matching
0 references
0 references
0.8135209679603577
0 references
0.8076687455177307
0 references
0.8055222034454346
0 references
0.8039150238037109
0 references
