ISSN:
1436-4646
Keywords:
Primary 05C05
;
Secondary 60F15
;
Minimal matchings
;
subadditive processes
;
complete convergence
;
large deviations
;
asymptotic methods
;
relaxation methods
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A linear programming relaxation of the minimal matching problem is studied for graphs with edge weights determined by the distances between points in a Euclidean space. The relaxed problem has a simple geometric interpretation that suggests the name minimal semi-matching. The main result is the determination of the asymptotic behavior of the length of the minimal semi-matching. It is analogous to the theorem of Beardwood, Halton and Hammersley (1959) on the asymptotic behavior of the traveling salesman problem. Associated results on the length of non-random Euclidean semi-matchings and large deviation inequalities for random semi-matchings are also given.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01585699
Permalink
