Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871823 | Discrete Applied Mathematics | 2016 | 14 Pages |
Abstract
The K-partitioning problem consists in partitioning the vertices of a weighted graph in K sets in order to minimize a function related to the edge weights. We introduce a linear mixed integer formulation with edge variables and representative variables. We investigate the polyhedral combinatorics of the problem, study several families of facet-defining inequalities and evaluate their efficiency on the linear relaxation.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zacharie Ales, Arnaud Knippel, Alexandre Pauchet,