Geodesic
Polytops of binary trees, structure of the polytop for the >--tree
Čebyševskij sbornik, Tome 23 (2022) no. 4, pp. 136-151.

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

In the paper minimal fillings of finite metric spaces are investigated. This object appeared as a generalization of the concepts of a shortest tree and a minimal filling in the sense of Gromov. It is known that the weight of a minimal filling of a given type can be found by linear programming and by so-called multitours technique. A relation between theses two approaches can be demonstrated using duality in linear programming, namely, rational points of the polytop constructed by the dual problem correspond to multitours. The paper is devoted to investigation of such polytopes, It is shown that the vertices of the polytop are in one-to-one correspondence with irreducible multitours. A description of the polytop and an explicit formula for the weight of the minimal filling of the «snake–type» binary tree is obtained.
Keywords: finite metric space, minimal filling, linear programming, duality, convex polytops. 
@article{CHEB_2022_23_4_a11,
     author = {O. S. Shcherbakov},
     title = {Polytops of binary trees, structure of the polytop for the <<snake--type>>--tree},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {136--151},
     publisher = {mathdoc},
     volume = {23},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2022_23_4_a11/}
}
TY  - JOUR
AU  - O. S. Shcherbakov
TI  - Polytops of binary trees, structure of the polytop for the <>--tree
JO  - Čebyševskij sbornik
PY  - 2022
SP  - 136
EP  - 151
VL  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2022_23_4_a11/
LA  - ru
ID  - CHEB_2022_23_4_a11
ER  - 
%0 Journal Article
%A O. S. Shcherbakov
%T Polytops of binary trees, structure of the polytop for the <>--tree
%J Čebyševskij sbornik
%D 2022
%P 136-151
%V 23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2022_23_4_a11/
%G ru
%F CHEB_2022_23_4_a11
O. S. Shcherbakov. Polytops of binary trees, structure of the polytop for the <>--tree. Čebyševskij sbornik, Tome 23 (2022) no. 4, pp. 136-151. http://geodesic.mathdoc.fr/item/CHEB_2022_23_4_a11/

[1] Ivanov A.O., Tuzhilin A.A., Teoriya ekstremalnykh setei, Institut kompyuternykh issledovanii, M.-Izhevsk, 2003

[2] Ivanov A.O., Tuzhilin A.A., “Odnomernaya problema Gromova o minimalnom zapolnenii”, Matem. sb., 203:5 (2012), 65–118 | DOI | MR | Zbl

[3] Ivanov A., Tuzhilin A., “Dual Linear Programming Problem and One-Dimensional Gromov Minimal Fillings of Finite Metric Space”, Differential Equations on Manifolds and Mathematical Physics, Trends in Mathematics, Birkhäuser, Cham, 2022, 165–182 | MR

[4] Eremin A.Yu., “Formula vesa minimalnogo zapolneniya konechnogo metricheskogo prostranstva”, Matem. sb., 204:9 (2013), 51–72 | DOI | MR | Zbl

[5] Vasilev F.P., Ivanitskii A.Yu., Lineinoe programmirovanie, MTsNMO, M., 2020

[6] Ivanov A.O., Tuzhilin A.A. Eremin A.Yu. i dr., “Minimalnye zapolneniya psevdometricheskikh prostranstv”, Trudy seminara po vektornomu i tenzornomu analizu s ikh prilozheniyami k geometrii, mekhanike i fizike, 27, 2011, 83–105

[7] Ivanov A. O.,Ovsyannikov Z. N., Strelkova N. P., Tuzhilin A. A., “Odnomernye minimalnye zapolneniya s rebrami otritsatelnogo vesa”, Vestn. Mosk. univ., Matem. Mekh., 2012, no. 5, 3–8

[8] Ivanov A. O., Tuzhilin A. A., Tsislik D., “Otnoshenie Shteinera dlya mnogoobrazii”, Matem. zametki, 74:3 (2003), 387–395 | DOI | MR | Zbl

[9] Ovsyannikov Z.N., “Otkrytoe semeistvo mnozhestv, dlya kotorykh minimalnoe zapolnenie ne edinstvenno”, Fund. i prikl. matem., 18:2 (2013), 153–156

[10] Bednov B. B., “Dlina minimalnogo zapolneniya pyatitochechnogo metricheskogo prostranstva”, Vestn. Mosk. univ., Matem. Mekh., 2017, no. 6, 3–8 | MR | Zbl

[11] Bednov B. B., “O mnozhestve tochek Shteinera chetyrekh elementov v prostranstve Lindenshtraussa”, Vestn. Mosk. univ., Matem. mekh., 2019, no. 6, 3–8 | MR | Zbl

[12] Bednov B. B., “Dlina minimalnogo zapolneniya tipa zvezdy”, Matem. sb., 207:8 (2016), 31–46 | DOI | MR | Zbl

[13] Bednov B. B., Borodin P. A., “Banakhovy prostranstva, realizuyuschie minimalnye zapolneniya”, Matem. sb., 205:4 (2014), 3–20 | DOI | MR | Zbl

[14] Pakhomova A. S., “Kriterii nepreryvnosti otnoshenii tipa Shteinera v prostranstve Gromova-Khausdorfa”, Matem. zametki, 96:1 (2014), 126–137 | DOI | MR | Zbl

[15] Rubleva O.V., “Kriterii additivnosti konechnogo metricheskogo prostranstva i minimalnye zapolneniya”, Vestn. Mosk. univ., Matem. Mekh., 2012, no. 2, 8–11 | MR | Zbl