Geodesic
Boolean quadric polytopes are faces of linear ordering polytopes
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 640-646.

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

Let $P_{\mathrm{BQP}}(n)$ be a boolean quadric polytope, $n\in\mathbb{N}$, $P_{\,\mathrm{LO}}(m)$ — linear ordering polytope, $m\in\mathbb{N}$. It is shown that $P_{\mathrm{\,BQP}}(n)$ is affine equivalent to a face of $P_{\,\mathrm{LO}}(2n)$.
Keywords: boolean quadric polytope, linear ordering polytope, stable set polytope, double covering polytope
Mots-clés : affine equivalence. 
@article{SEMR_2017_14_a73,
     author = {A. N. Maksimenko},
     title = {Boolean quadric polytopes are faces of linear ordering polytopes},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {640--646},
     publisher = {mathdoc},
     volume = {14},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2017_14_a73/}
}
TY  - JOUR
AU  - A. N. Maksimenko
TI  - Boolean quadric polytopes are faces of linear ordering polytopes
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2017
SP  - 640
EP  - 646
VL  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2017_14_a73/
LA  - ru
ID  - SEMR_2017_14_a73
ER  - 
%0 Journal Article
%A A. N. Maksimenko
%T Boolean quadric polytopes are faces of linear ordering polytopes
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2017
%P 640-646
%V 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2017_14_a73/
%G ru
%F SEMR_2017_14_a73
A. N. Maksimenko. Boolean quadric polytopes are faces of linear ordering polytopes. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 640-646. http://geodesic.mathdoc.fr/item/SEMR_2017_14_a73/

[1] M.M. Deza, M. Laurent, Geometry of cuts and metrics, Springer, 1997 | MR | Zbl

[2] S. Fiorini, “How to recycle your facets”, Discrete Optimization, 3 (2006), 136–153 | DOI | MR | Zbl

[3] S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, R. de Wolf, “Exponential Lower Bounds for Polytopes in Combinatorial Optimization”, J. ACM, 62:2 (2015), 17 | DOI | MR | Zbl

[4] V. Kaibel, S. Weltge, “A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially”, Discrete and Computational Geometry, 53 (2015), 397–401 | DOI | MR | Zbl

[5] R.M. Karp, “Reducibility among combinatorial problems”, Complexity of computer computations, 1972, 85–103 | DOI | MR

[6] M.M. Kovalev, G.G. Bolotashvili, “Extension of a special class of facets for the polytope of the linear ordering problem”, Doklady of the National academy of sciences of Belarus, 56:5 (2012), 20–24 | MR | Zbl

[7] A.N. Maksimenko, “An analog of the Cook theorem for polytopes”, Russian Mathematics, 56 (2012), 28–34 | DOI | MR | Zbl

[8] A. Maksimenko, “$k$-Neighborly faces of the Boolean quadric polytopes”, Journal of Mathematical Sciences, 203 (2014), 816–822 | DOI | MR | Zbl

[9] A. Maksimenko, “The common face of some 0/1-polytopes with NP-complete nonadjacency relation”, Journal of Mathematical Sciences, 203 (2014), 823–832 | DOI | MR | Zbl

[10] A.N. Maksimenko, “A special role of Boolean quadratic polytopes among other combinatorial polytopes”, Model. Anal. Inform. Sist., 23 (2016), 23–40 | DOI | MR

[11] H.P. Young, “On permutations and permutation polytopes”, Polyhedral combinatorics, 8 (1978), 128–140 | DOI | MR | Zbl