The volume of relaxed Boolean-quadric and cut polytopes

✍ Scribed by Chun-Wa Ko; Jon Lee; Einar Steingrímsson

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 230 KB
• Volume: 163
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00343-u

✦ Synopsis

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 O, for all hj in N. In a first step toward seeing how well 3. approximates ~. we estabhsh that the d-dimensional volume of ~ is 22*-dn!/(2n)!. Using a well-known connection between ,~ and the 'cut polytope' of a complete graph on n + 1 vertices, we also establish the volume of a relaxation of this cut polytope.