Boolean quadric polytopes are faces of linear ordering polytopes

DOI10.17377/SEMI.2017.14.055MaRDI QIDQ2403680zbMATH OpenOpenAlexFDO

Authors Aleksandr N. Maksimenko

Publication date 11 September 2017

Published in Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.06170

zbMATH Keywords

affine equivalencestable set polytopeBoolean quadric polytopelinear ordering polytopedouble covering polytope

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: Let $BQP(n)$ be a boolean quadric polytope, $LOP(m)$ be a linear ordering polytope. It is shown that $BQP(n)$ is linearly isomorphic to a face of $LOP(2n)$.

Recommendations

• \(k\)-neighborly faces of the Boolean quadric polytopes
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The cut polytope and the Boolean quadric polytope
• scientific article; zbMATH DE number 431488
• A note on the Boolean quadric polytope

Cites work

• scientific article; zbMATH DE number 3659595 (Why is no real title available?)
• scientific article; zbMATH DE number 202575 (Why is no real title available?)
• scientific article; zbMATH DE number 6745104 (Why is no real title available?)
• A new proof of Gromov’s theorem on groups of polynomial growth
• A short proof that the extension complexity of the correlation polytope grows exponentially
• An analog of the Cook theorem for polytopes
• Exponential lower bounds for polytopes in combinatorial optimization
• Geometry of cuts and metrics
• How to recycle your facets
• Reducibility among combinatorial problems
• The common face of some 0/1-polytopes with NP-complete nonadjacency relation
• \(\Phi\)-harmonic functions on discrete groups and the first \(\ell^\Phi\)-cohomology
• \(k\)-neighborly faces of the Boolean quadric polytopes

Cited in

(4)

• Extended formulations for order polytopes through network flows
• Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes
• \(k\)-neighborly faces of the Boolean quadric polytopes
• scientific article; zbMATH DE number 431488 (Why is no real title available?)

This page was built for publication: Boolean quadric polytopes are faces of linear ordering polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2403680)