Geodesic
Combinatorial Optimization Problems in Ultrametric Spaces
Teoretičeskaâ i matematičeskaâ fizika, Tome 136 (2003) no. 1, pp. 164-176 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study the solutions of some known combinatorial optimization problems including the minimum matching problem, the minimum spanning tree problem, and the traveling salesman problem in $d$-dimensional $p$-adic spaces. It appears that the greedy algorithms yield the optimal solutions of these problems in the ultrametric space, which allows obtaining explicit expressions for the estimates of their averages. We study the asymptotic behavior of these averages as the number of points increases infinitely and find some similarities to the Euclidean case, as well as new, unexpected properties.
Keywords: traveling salesman problem, minimum matching, ultrametricity, greedy algorithms, renormalization group, self-averaging property.
Mots-clés : $p$-adic spaces 
@article{TMF_2003_136_1_a10,
     author = {M. D. Missarov and R. G. Stepanov},
     title = {Combinatorial {Optimization} {Problems} in {Ultrametric} {Spaces}},
     journal = {Teoreti\v{c}eska\^a i matemati\v{c}eska\^a fizika},
     pages = {164--176},
     year = {2003},
     volume = {136},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TMF_2003_136_1_a10/}
}
TY  - JOUR
AU  - M. D. Missarov
AU  - R. G. Stepanov
TI  - Combinatorial Optimization Problems in Ultrametric Spaces
JO  - Teoretičeskaâ i matematičeskaâ fizika
PY  - 2003
SP  - 164
EP  - 176
VL  - 136
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TMF_2003_136_1_a10/
LA  - ru
ID  - TMF_2003_136_1_a10
ER  - 
%0 Journal Article
%A M. D. Missarov
%A R. G. Stepanov
%T Combinatorial Optimization Problems in Ultrametric Spaces
%J Teoretičeskaâ i matematičeskaâ fizika
%D 2003
%P 164-176
%V 136
%N 1
%U http://geodesic.mathdoc.fr/item/TMF_2003_136_1_a10/
%G ru
%F TMF_2003_136_1_a10
M. D. Missarov; R. G. Stepanov. Combinatorial Optimization Problems in Ultrametric Spaces. Teoretičeskaâ i matematičeskaâ fizika, Tome 136 (2003) no. 1, pp. 164-176. http://geodesic.mathdoc.fr/item/TMF_2003_136_1_a10/

[1] M. Mezard, G. Parisi, M. Virasoro, Spin-Glass Theory and All Beyond, World Sci. Lect. Notes Phys., 9, World Scientific, Singapore, 1987 ; S. Kirkpatrik, G. Toulouse, J. Physique, 46 (1985), 1277–1292 | MR | Zbl | DOI | MR

[2] J. Beardwood, J. H. Halton, J. M. Hammersley, Proc. Cambridge Philos. Soc., 55 (1959), 299–327 ; J. M. Steele, Probability Theory and Combinatorial Optimization, SIAM, Philadelphia, 1997 ; J. Yukich, “Quasi-additive Euclidean functionals”, Discrete Probability and Algorithms, Proc. of the Workshops “Probability and Algorithms” and “The Finite Markov Chain Renaissance” (IMA, Univ. of Minnesota, Minneapolis, MN, USA, 1993), IMA Vol. Math. Appl., 72, eds. D. Aldous et al., Springer, New York, 1995, 149–158 | DOI | MR | Zbl | MR | Zbl | DOI | MR | Zbl

[3] P. M. Bleher, Ya. G. Sinai, Commun. Math. Phys., 33 (1973), 23–42 | DOI | MR

[4] M. D. Missarov, TMF, 114:3 (1998), 323–336 ; 117:3, 471–488 | DOI | MR | Zbl | MR | Zbl

[5] I. V. Volovich, TMF, 71 (1987), 337–340 ; В. С. Владимиров, И. В. Волович, Е. И. Зеленов, $p$-Адический анализ и математическая физика, Наука, М., 1994 | MR | Zbl | MR | Zbl

[6] E. Yu. Lerner, M. D. Missarov, Commun. Math. Phys., 32 (1989), 347–356