  


Size constrained graph partitioning polytope. Part I: Dimension and trivial facets
F. Aykut Özsoy (fozsoyulb.ac.be) Abstract: We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several wellknown graph partitioning problems from the literature like the clique partitioning problem, the equipartition problem and the kway equipartition problem. In this paper and its sequel, we analyze the structure of the corresponding polytope and prove several results concerning the facial structure. Our analysis yields important results for the closely related equipartition and kway equipartition polytopes as well. Keywords: graph partitioning polytope, clique partitioning, kway equipartition, equipartition, integer programming, polyhedra Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Integer Programming (01 Programming ) Citation: Technical Reports of the ULB Computer Science Department, Number 577, Brussels, Belgium, August 2007. Download: [PDF] Entry Submitted: 01/08/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  