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 journalArticleAcademicpeer-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 languageEnglish
Pages (from-to)235-243
JournalOperations Research Letters
Volume24
DOIs
Publication statusPublished - 1999
Externally publishedYes

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