Abstract
| Original language | English |
|---|---|
| Pages (from-to) | 235-243 |
| Journal | Operations Research Letters |
| Volume | 24 |
| DOIs | |
| Publication status | Published - 1999 |
| Externally published | Yes |
Fingerprint
Cite this
}
Lifting theorems and facet characterization for a class of clique partitioning inequalities. / Bandelt, H.J.; Oosten, M.; Rutten, J.H.G.C.; Spieksma, F.C.R.
In: Operations Research Letters, Vol. 24, 1999, p. 235-243.Research output: Contribution to journal › Article › Academic › peer-review
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 -