Lifting theorems and facet characterization for a class of clique partitioning inequalities
type: Item
instance of: scholarly article
title: Lifting theorems and facet characterization for a class of clique partitioning inequalities
zbMATH Open document ID: 0941.90072
DOI: 10.1016/S0167-6377(99)00029-2
author: Hans-Jürgen Bandelt
author: Maarten Oosten
author: Jeroen H. G. C. Rutten
author: Frits C. R. Spieksma
published in: Operations Research Letters
publication date: 1999-12-19T00:00:00Z
review text: 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 compact graph \(K_m\) on \(m\) vertices, it defines a facet for the polytope corresponding to \(K_n\) 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.
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 1347263
zbMATH Keywords: polyhedral combinatorics
zbMATH Keywords: facets
zbMATH Keywords: lifting
zbMATH Keywords: clique partitioning
MaRDI profile type: Publication
cites work: The partition problem
cites work: Q4369763
cites work: Q3753826
cites work: Facets of the clique partitioning polytope
cites work: Q3972001
cites work: Q3859790
cites work: Q4040221
full work available at URL: s0167-6377(99)00029-2
OpenAlex ID: W1966088050
description: scientific article; zbMATH DE number 1347263