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 | |
State | Published - Mar 1 1993 |
Keywords
- Graph partition
- facet
- multiway cut
- polytope
ASJC Scopus subject areas
- Software
- Mathematics(all)