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.
Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.

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

VL - 61

SP - 27

EP - 48

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1

ER -