Ergodic theorems for some classical problems in combinatorial optimization
Yukich, J. E.
Ann. Appl. Probab., Tome 6 (1996) no. 1, p. 1006-1023 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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.
Publié le : 1996-08-14
Classification:  Subadditive ergodic theorems,  combinatorial optimization,  minimal spanning tree,  traveling salesman problem,  boundary process,  60F15,  60D05,  60C05 
@article{1034968238,
     author = {Yukich, J. E.},
     title = {Ergodic theorems for some classical problems in combinatorial
		 optimization},
     journal = {Ann. Appl. Probab.},
     volume = {6},
     number = {1},
     year = {1996},
     pages = { 1006-1023},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1034968238}
}

Yukich, J. E. Ergodic theorems for some classical problems in combinatorial
		 optimization. Ann. Appl. Probab., Tome 6 (1996) no. 1, pp.  1006-1023. http://gdmltest.u-ga.fr/item/1034968238/