Facets of the k-partition polytope

Sunil Chopra*, M. R. Rao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)27-48
Number of pages22
JournalDiscrete Applied Mathematics
Volume61
Issue number1
DOIs
StatePublished - Jul 7 1995

Keywords

  • Facet
  • Lifting
  • Valid inequality
  • k-partition polytope

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Facets of the k-partition polytope'. Together they form a unique fingerprint.

Cite this