✦ LIBER ✦

The cut polytope and the Boolean quadric polytope

✍ Scribed by Caterina De Simone

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 264 KB
Volume: 79
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90056-n

No coin nor oath required. For personal study only.

✦ Synopsis

In 1983 Barahona defined the class of cut polytopes; recently Padberg defined the class of Boolean quadric polytopes.

We show that every Boolean quadric polytope is the image of a cut polytope under a bijective linear transformation, and so studying Boolean quadric polytopes reduces to studying special cut polytopes.

Our proof uses an idea introduced in 1965 by Hammer.

📜 SIMILAR VOLUMES

The volume of relaxed Boolean-quadric an

The volume of relaxed Boolean-quadric and cut polytopes

✍ Chun-Wa Ko; Jon Lee; Einar Steingrímsson 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

For n ~> 2, the boolean quadric polytope ~, is the convex hull in d:= (~ l) dimensions of the binary solutions xixj = Yo, for all i < j in N := { I. 2 ..... n}. The polytope is naturally modeled by a somewhat larger polytope; namely, .~ the solution set of Yo <~x~, yo<~xj. x~ + xj <<. 1 + Yo, Yo >1

Gap Inequalities for the Cut Polytope

✍ Monique Laurent; Svatopluk Poljak 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 437 KB

Lifting facets of the cut polytope

✍ Caterina De Simone 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 229 KB

On a positive semidefinite relaxation of

On a positive semidefinite relaxation of the cut polytope

✍ Monique Laurent; Svatopluk Poljak 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 937 KB

Establishing the matching polytope

✍ M.L Balinski 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 596 KB

Fiber Polytopes for the Projections betw

Fiber Polytopes for the Projections between Cyclic Polytopes

✍ Christos A. Athanasiadis; Jesús A. De Loera; Victor Reiner; Francisco Santos 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 359 KB

The cyclic polytope C (n, d) is the convex hull of any n points on the moment curve {(t, t 2 , . . . , t d ) : we consider the fiber polytope (in the sense of Billera and Sturmfels [6]) associated to the natural projection of cyclic polytopes π : C(n, d ) → C(n, d) which 'forgets' the last dd coord