𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Lifting facets of the cut polytope

✍ Scribed by Caterina De Simone

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
229 KB
Volume
9
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The cut polytope and the Boolean quadric
The cut polytope and the Boolean quadric polytope
✍ Caterina De Simone πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 264 KB

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 spe

Gap Inequalities for the Cut Polytope
Gap Inequalities for the Cut Polytope
✍ Monique Laurent; Svatopluk Poljak πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 437 KB
Stability critical graphs and ranks face
Stability critical graphs and ranks facets of the stable set polytope
✍ E.C. Sewell; L.E. Trotter Jr. πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 616 KB

Rank inequalities due to stability critical (u-critical) graphs are used to develop a finite nested sequence of linear relaxations of the stable set polytope, the strongest of which provides an integral max-min relation: In a simple graph, the maximum size of a stable set is equal to the minimum (we