ERGODIC THEOREMS FOR SOME CLASSICAL PROBLEMS IN COMBINATORIAL OPTIMIZATION
成果类型：
Article
署名作者：
Yukich, J. E.
署名单位：
Lehigh University
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
发表日期：
1996
页码：
1006-1023
关键词：
摘要：
We show that the stochastic versions of some classical problems in combinatorial optimization may be imbedded in multiparameter subadditive processes having an intrinsic ergodic structure. A multiparameter generalization of Kingman's subadditive ergodic theorem is used to capture strong laws for these optimization problems, including the traveling salesman and minimal spanning tree processes. In this way we make progress on some open problems and provide alternate proofs of some well known asymptotic results.