Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
8 Probability and Problems in Euclidean Combinatorial Optimization
8 Probability and Problems in Euclidean Combinatorial Optimization
Pages 109-130
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 109... ...
the approximation and determination of constants whose existence is known by subadditive methods, (2) the central limit problems for several functionals closely related to Euclidean functionals, and (3)
|
From page 110... ...
et al., 1959) If Xi, ~ < i < on are independently and identically distributed random variables with bounded support in R&, then the length in under the usual Euclidean metric of the shortest path through the points {X~,X2,...,Xn)
|
From page 111... ...
We first consider the theory of the minimal spanning tree (MST3 and review how one can construct an infinite analog to the MST that leads to answers of a number of classical questions. One of the best reasons for introducing any new mathematical structure is that it simplifies and strengthens earlier results, and this is exactly what occurs in this development of an "infinite MST." The new structure permits one to make many deductions that are apparently difficult (or perhaps impossible)
|
From page 112... ...
Moreover, it generated powerful interest in the BHH theorem, its generalizations, and sharpenings that are at the center of this survey. S.2 Subadclitive Eucliclean Functionals By abstracting from the traveling salesman tour just a few of its basic properties, it is possible to suggest a very general result that provides information comparable to that given by the BHH theorem for a large number of problems of combinatorial optimization in Euclidean space.
|
From page 113... ...
This class of processes seems to abstract the most essential features of the TSP that are needed for an effective asymptotic analysis of the functional applied to finite samples of independent random variables with values in R3. To see how subadditive Euclidean functionals arise (and to see how some problems just barely elude the framework)
|
From page 114... ...
Still, one cannot be long content with a theory confined to uniformly distributed random variables. Fortunately, with the addition of just a couple of additional constraints, the limit theory of subadditive Euclidean functionals can be extended to quite generally distributed variables.
|
From page 115... ...
Lemma 1 Let L be a monotone subadditive Euclidean functional that is scale-bounded (~.5} and simply subadditive f8.6~. If {Xi} are independent identically distributed ri.i.~.; random variables and E is any Funded set of Lebesgue measure zero, then as n ~ oo t({X~,X2,.
|
From page 116... ...
has provided a set of results that cast new light on the role of dimension in problems like the TSP by developing limit results for TSP tours in fractal spaces. I`alley considered finite random samples chosen uniformly
|
From page 117... ...
3.5 Minimal Spanning bees If x = {x~,...,xn) is a finite set of points i spanning tree (MST)
|
From page 118... ...
The basic philosophy that guided the analysis is that because the empirical distributions of any independent uniform sequences look locally like a realization of the Poisson process, one should be able to relate the MST of a uniform sample to the MST of the (unbounded) Poisson process.
|
From page 119... ...
be the graph on an infinite nice vertex set x defined by taking (~,x2) as an edge in g if it is an edge in either too~x~,x)
|
From page 120... ...
The matching problem is intermediate in complexity between the MST problem and the TSP. The minimal matching problem cannot be solved by a naive greedy algorithm such as that used for the MST, but there is still a polynomial-time algorithm that does solve the problem in contrast to the TSP.
|
From page 121... ...
Still, the basic motivation remains substantially intact, and for ~ ~ 3 one again finds the characteristic growth rates of no/. As an added impetus to the theory of Euclidean matching, there are some powerful connections with other parts of combinatorial optimization.
|
From page 122... ...
was to develop the concrete tools of the theory of majorizing measures that make it directly useful in the theory of Mn and Do and then to show how those tools could be used to deepen and unify the investigations initiated by Ajtai, KomIos, and Tusnady and broadened by Leighton and Shor. S.7 The Values of the Constants There is a long history of effort devoted to the determination of the limiting constraints in results like the BHH theorem.
|
From page 123... ...
Other than these bounds, little progress concerning the AL ~ was made until Bertsimas and van Ryzin (1990) developed exact expressions for the probabilistic minimum spanning tree and matching constants as ~ gets large.
|
From page 124... ...
3.9 Worst-Case Growth Rates One engaging aspect of the asymptotic theory of combinatorial optimization of point functionals is the persistent similarity between the probabilistic rates of growth that have been reviewed and the behavior of the corresponding function~s in worst-case settings. As a primary example of a worst-case growth rate, consider the worstcase length of an optimal traveling salesman tour in the unit d-cube: pT n = m m n ~ e: T is a our of SO .
|
From page 125... ...
, minimum spanning trees (Steele and Snyder, 1989) , greedy matchings (Snyder and Steele, 1990)
|
From page 126... ...
that is devoted to the topic. Galileo is supposed to have said, "To study science, one must speak the language of science, and the language of science is written in circles, lines, and squares." With luck, this survey reveals that there is something a priori appropriate about the probability theory of combinatorial optimization.
|
From page 127... ...
, Asymptotics of Euclidean minimal spanning trees on random samples, to appear in Probability and Related Fields. Avram, F., and D
|
From page 128... ...
(1991) , A note on lower bounds for rectilinear Steiner trees, Technical Report, Department of Computer Science, University of Virginia, Charlottesville, Va.
|
From page 129... ...
(198Ib) , Subadditive Euclidean functionals and non-linear growth in geometric probability, Ann.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.