zbMATH — the first resource for mathematics

Analysis of probabilistic combinatorial optimization problems in Euclidean spaces. (English) Zbl 0777.90048
The objective of this paper is to present general finite-size bounds and limit theorems for the objective functions of the probabilistic traveling salesman problem (PTSP) and probabilistic minimum spanning tree problem. For example, the following theorem concerning PTSP is proved: Let \((X_ i)_ i\) be an infinite sequence of points independently and uniformly distributed over \([0,1]^ 2\) and \(p\) be the probability of existence of each point. Then there exists a positive constant \(c(p)\) such that \[ \lim_{n\to\infty}{El^{ptsp}_ p(X^{(n)})\over\sqrt n}=c(p)\qquad\text{(a.s.)}, \] \(El^{ptsp}_ p(X^{(n)})\) denotes the expected length of the tour and for \(c(p)\) only bounds are known: \(5p/8\leq c(p)\leq\sqrt{4p/3}\). The author also discusses the practical implications of the presented results and indicates some open problems. The paper presupposes a good familiarity with the probabilistic versions of the well known problems; it lacks clear and precise problem formulations.
Reviewer: I.Martinec (Praha)

90C27 Combinatorial optimization
90B15 Stochastic network models in operations research
90C15 Stochastic programming
Full Text: DOI