TY - JOUR
T1 - Facets of the k-partition polytope
AU - Chopra, Sunil
AU - Rao, M. R.
N1 - Funding Information:
* Corresponding author. ’ Supported in part by NSF Grant DDM8800281 and DDM9001705.
PY - 1995/7/7
Y1 - 1995/7/7
N2 - We study facets of the k-partition polytope Pk,n, the convex hull of edges cut by r-partitions of a complete graph for r ≤ k, k ≥ 3. We generalize the hypermetric and cycle inequalities (see Deza and Laurent, 1992) from the cut polytope to Pk,n, k ≥ 3. We give some sufficient conditions under which these are facet defining. We show the anti-web inequality introduced by Deza and Laurent (1992) to be facet defining for Pk,n, k ≥ 3. We also give lifting procedures for constructing facets of Pk,r from facets of Pk,n for r ≥ n + 1 and facets of Pk,r from facets of Pk-1,n for r ≥ n + 1.
AB - We study facets of the k-partition polytope Pk,n, the convex hull of edges cut by r-partitions of a complete graph for r ≤ k, k ≥ 3. We generalize the hypermetric and cycle inequalities (see Deza and Laurent, 1992) from the cut polytope to Pk,n, k ≥ 3. We give some sufficient conditions under which these are facet defining. We show the anti-web inequality introduced by Deza and Laurent (1992) to be facet defining for Pk,n, k ≥ 3. We also give lifting procedures for constructing facets of Pk,r from facets of Pk,n for r ≥ n + 1 and facets of Pk,r from facets of Pk-1,n for r ≥ n + 1.
KW - Facet
KW - Lifting
KW - Valid inequality
KW - k-partition polytope
UR - http://www.scopus.com/inward/record.url?scp=0347566655&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0347566655&partnerID=8YFLogxK
U2 - 10.1016/0166-218X(93)E0175-X
DO - 10.1016/0166-218X(93)E0175-X
M3 - Article
AN - SCOPUS:0347566655
SN - 0166-218X
VL - 61
SP - 27
EP - 48
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 1
ER -