ANALYSIS OF PROBABILISTIC COMBINATORIAL OPTIMIZATION PROBLEMS IN EUCLIDEAN SPACES

• 成果类型: Article
• 署名作者: JAILLET, P
• 署名单位: University of Texas System; University of Texas Austin
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.18.1.51
• 发表日期: 1993
• 页码: 51-70
• 关键词: growth

摘要

Probabilistic combinatorial optimization problems are generalized versions of deterministic combinatorial optimization problems with explicit inclusion of probabilistic elements in the problem definitions. Based on the probabilistic traveling salesman problem (PTSP) and on the probabilistic minimum spanning tree problem (PMSTP), the objective of this paper is to give a rigorous treatment of the probabilistic analysis of these problems in the plane. More specifically we present general finite-size bounds and limit theorems for the objective functions of the PTSP and PMSTP. We also discuss the practical implications of these results and indicate some open problems.