Article ID Journal Published Year Pages File Type
6871823 Discrete Applied Mathematics 2016 14 Pages PDF
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
, , ,