The partition problem

Sunil Chopra; M. R. Rao

doi:10.1007/BF01581239

The partition problem

Sunil Chopra^*, M. R. Rao

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

146 Scopus citations

Abstract

In this paper we describe several forms of the k-partition problem and give integer programming formulations of each case. The dimension of the associated polytopes and some basic facets are identified. We also give several valid and facet defining inequalities for each of the polytopes.

Original language	English (US)
Pages (from-to)	87-115
Number of pages	29
Journal	Mathematical Programming
Volume	59
Issue number	1-3
DOIs	https://doi.org/10.1007/BF01581239
State	Published - Mar 1 1993
Externally published	Yes

Keywords

Graph partition
facet
multiway cut
polytope

ASJC Scopus subject areas

Software
Mathematics(all)

Access to Document

10.1007/BF01581239

Cite this

@article{9e4c6e9057314d168c1a0c6b39c9f98b,

title = "The partition problem",

abstract = "In this paper we describe several forms of the k-partition problem and give integer programming formulations of each case. The dimension of the associated polytopes and some basic facets are identified. We also give several valid and facet defining inequalities for each of the polytopes.",

keywords = "Graph partition, facet, multiway cut, polytope",

author = "Sunil Chopra and Rao, {M. R.}",

year = "1993",

month = mar,

day = "1",

doi = "10.1007/BF01581239",

language = "English (US)",

volume = "59",

pages = "87--115",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1-3",

}

TY - JOUR

T1 - The partition problem

AU - Chopra, Sunil

AU - Rao, M. R.

PY - 1993/3/1

Y1 - 1993/3/1

N2 - In this paper we describe several forms of the k-partition problem and give integer programming formulations of each case. The dimension of the associated polytopes and some basic facets are identified. We also give several valid and facet defining inequalities for each of the polytopes.

AB - In this paper we describe several forms of the k-partition problem and give integer programming formulations of each case. The dimension of the associated polytopes and some basic facets are identified. We also give several valid and facet defining inequalities for each of the polytopes.

KW - Graph partition

KW - facet

KW - multiway cut

KW - polytope

UR - http://www.scopus.com/inward/record.url?scp=0027557258&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027557258&partnerID=8YFLogxK

U2 - 10.1007/BF01581239

DO - 10.1007/BF01581239

M3 - Article

AN - SCOPUS:0027557258

VL - 59

SP - 87

EP - 115

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-3

ER -

The partition problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this