|
Gromov–Hausdorff distances to simplexes and some applications to discrete optimisation
A. O. Ivanovab, A. A. Tuzhilina a Faculty of Mechanics and Mathematics, Lomonosov
Moscow State University (Moscow)
b Bauman Moscow State Technical University (Moscow)
Abstract:
Relations between Gromov–Hausdorff distance and Discrete Optimisation problems are discussed. We use the Gromov–Hausdorff distances to single-distance metric space for solving the following problems: calculation of lengths of minimum spanning tree edges of a finite metric space; generalised Borsuk problem; chromatic number and clique cover number of a simple graph calculation problems.
Keywords:
Gromov–Hausdorff distance, minimum spanning tree, Borsuk problem, chromatic number, clique covering, metric geometry, discrete optimisation.
Received: 08.12.2019 Accepted: 11.03.2020
Citation:
A. O. Ivanov, A. A. Tuzhilin, “Gromov–Hausdorff distances to simplexes and some applications to discrete optimisation”, Chebyshevskii Sb., 21:2 (2020), 169–189
Linking options:
https://www.mathnet.ru/eng/cheb903 https://www.mathnet.ru/eng/cheb/v21/i2/p169
|
Statistics & downloads: |
Abstract page: | 113 | Full-text PDF : | 50 | References: | 26 |
|