|
This article is cited in 3 scientific papers (total in 3 papers)
Combinatorial Optimization Problems in Ultrametric Spaces
M. D. Missarov, R. G. Stepanov Kazan State University
Abstract:
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, $p$-adic spaces, self-averaging property.
Received: 15.05.2002
Citation:
M. D. Missarov, R. G. Stepanov, “Combinatorial Optimization Problems in Ultrametric Spaces”, TMF, 136:1 (2003), 164–176; Theoret. and Math. Phys., 136:1 (2003), 1037–1047
Linking options:
https://www.mathnet.ru/eng/tmf209https://doi.org/10.4213/tmf209 https://www.mathnet.ru/eng/tmf/v136/i1/p164
|
Statistics & downloads: |
Abstract page: | 424 | Full-text PDF : | 200 | References: | 53 | First page: | 1 |
|