Geodesic
Combinatorial Optimization Problems in Ultrametric Spaces
Teoretičeskaâ i matematičeskaâ fizika, Tome 136 (2003) no. 1, pp. 164-176

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {136},
     number = {1},
     year = {2003},
     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
PB  - mathdoc
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
%I mathdoc
%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/