Lifting theorems and facet characterization for a class of clique partitioning inequalities

H.J. Bandelt; M. Oosten; J.H.G.C. Rutten; F.C.R. Spieksma

doi:10.1016/S0167-6377(99)00029-2

Lifting theorems and facet characterization for a class of clique partitioning inequalities

H.J. Bandelt, M. Oosten, J.H.G.C. Rutten, F.C.R. Spieksma

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

In this paper we prove two lifting theorems for the clique partitioning polytope, which provide sufficient conditions for a valid inequality to be facet-defining. In particular, if a valid inequality defines a facet of the polytope corresponding to the complete graph Km on m vertices, it defines a facet for the polytope corresponding to Kn for all n>m. This answers a question raised by Grötschel and Wakabayashi. Further, for the case of arbitrary graphs, we characterize when the so-called 2-partition inequalities define facets

Original language	English
Pages (from-to)	235-243
Journal	Operations Research Letters
Volume	24
DOIs	https://doi.org/10.1016/S0167-6377(99)00029-2
Publication status	Published - 1999
Externally published	Yes

Access to Document

10.1016/S0167-6377(99)00029-2

Fingerprint Dive into the research topics of 'Lifting theorems and facet characterization for a class of clique partitioning inequalities'. Together they form a unique fingerprint.

Cite this

@article{8a6cd0a7a9e34cf29af827c466544654,

title = "Lifting theorems and facet characterization for a class of clique partitioning inequalities",

abstract = "In this paper we prove two lifting theorems for the clique partitioning polytope, which provide sufficient conditions for a valid inequality to be facet-defining. In particular, if a valid inequality defines a facet of the polytope corresponding to the complete graph Km on m vertices, it defines a facet for the polytope corresponding to Kn for all n>m. This answers a question raised by Gr{\"o}tschel and Wakabayashi. Further, for the case of arbitrary graphs, we characterize when the so-called 2-partition inequalities define facets",

author = "H.J. Bandelt and M. Oosten and J.H.G.C. Rutten and F.C.R. Spieksma",

year = "1999",

doi = "10.1016/S0167-6377(99)00029-2",

language = "English",

volume = "24",

pages = "235--243",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

}

TY - JOUR

T1 - Lifting theorems and facet characterization for a class of clique partitioning inequalities

AU - Bandelt, H.J.

AU - Oosten, M.

AU - Rutten, J.H.G.C.

AU - Spieksma, F.C.R.

PY - 1999

Y1 - 1999

N2 - In this paper we prove two lifting theorems for the clique partitioning polytope, which provide sufficient conditions for a valid inequality to be facet-defining. In particular, if a valid inequality defines a facet of the polytope corresponding to the complete graph Km on m vertices, it defines a facet for the polytope corresponding to Kn for all n>m. This answers a question raised by Grötschel and Wakabayashi. Further, for the case of arbitrary graphs, we characterize when the so-called 2-partition inequalities define facets

AB - In this paper we prove two lifting theorems for the clique partitioning polytope, which provide sufficient conditions for a valid inequality to be facet-defining. In particular, if a valid inequality defines a facet of the polytope corresponding to the complete graph Km on m vertices, it defines a facet for the polytope corresponding to Kn for all n>m. This answers a question raised by Grötschel and Wakabayashi. Further, for the case of arbitrary graphs, we characterize when the so-called 2-partition inequalities define facets

U2 - 10.1016/S0167-6377(99)00029-2

DO - 10.1016/S0167-6377(99)00029-2

M3 - Article

VL - 24

SP - 235

EP - 243

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

ER -