Geodesic
Hypergraphs of special type and CUT polytope relaxations properties analysis
Modelirovanie i analiz informacionnyh sistem, Tome 18 (2011) no. 3, pp. 82-100 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The topic of the research is a relationship between a class of hypergraphs of a special type and properties of the points of the cut polytope relaxations $M_{n,k}$. It is established that for a sufficiently large $n$ in $M_{n,4}$ and $M_{n,5}$ polytopes, there are points which have no integer vertices in any expansion in a convex combination of $M_{n,3}$ vertices.
Keywords: hypergraphs, cut polytope relaxations, rooted semimetric polytope, integrity recognition. 
@article{MAIS_2011_18_3_a8,
     author = {A. V. Nikolaev},
     title = {Hypergraphs of special type and {CUT} polytope relaxations properties analysis},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {82--100},
     year = {2011},
     volume = {18},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2011_18_3_a8/}
}
TY  - JOUR
AU  - A. V. Nikolaev
TI  - Hypergraphs of special type and CUT polytope relaxations properties analysis
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2011
SP  - 82
EP  - 100
VL  - 18
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MAIS_2011_18_3_a8/
LA  - ru
ID  - MAIS_2011_18_3_a8
ER  - 
%0 Journal Article
%A A. V. Nikolaev
%T Hypergraphs of special type and CUT polytope relaxations properties analysis
%J Modelirovanie i analiz informacionnyh sistem
%D 2011
%P 82-100
%V 18
%N 3
%U http://geodesic.mathdoc.fr/item/MAIS_2011_18_3_a8/
%G ru
%F MAIS_2011_18_3_a8
A. V. Nikolaev. Hypergraphs of special type and CUT polytope relaxations properties analysis. Modelirovanie i analiz informacionnyh sistem, Tome 18 (2011) no. 3, pp. 82-100. http://geodesic.mathdoc.fr/item/MAIS_2011_18_3_a8/

[1] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lektsii po teorii grafov, Nauka, M., 1990, 384 pp. | MR | Zbl

[2] M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[3] V. A. Bondarenko, “Ob odnom kombinatornom mnogogrannike”, Modelirovanie i analiz vychislitelnykh sistem, Sb. nauch. tr., Yarosl. gos. un-t, Yaroslavl, 1987, 133–134 | MR

[4] M. Deza, M. Loran, Geometriya razrezov i metrik, MTsNMO, M., 2001, 736 pp.

[5] M. V. Padberg, “The Boolean quadratic polytope: some characteristics, facets and relatives”, Mathematical Program., 45 (1989), 139–172 | DOI | MR | Zbl

[6] V. A. Bondarenko, A. N. Maksimenko, Geometricheskie konstruktsii i slozhnost v kombinatornoi optimizatsii, LKI, M., 2008, 184 pp.

[7] V. A. Bondarenko, B. V. Uryvaev, “Ob odnoi zadache tselochislennoi optimizatsii”, Avtomatika i telemekhanika, 6 (2007), 18–23 | MR | Zbl

[8] Thomas Christof, Andreas Loebel, PORTA: POlyhedron Representation Transformation Algorithm 1.4.0, The Konrad-Zuse-Zentrum fur Informationstechnik Berlin http://www.zib.de/Optimization/Software/Porta/