Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141422 | Discrete Optimization | 2015 | 11 Pages |
Abstract
We consider the problem of partitioning a graph into cliques of bounded cardinality. The goal is to find a partition that minimizes the sum of clique costs where the cost of a clique is given by a set function on the nodes. We present a general algorithmic solution based on solving the problem variant without the cardinality constraint. We obtain constant factor approximations depending on the solvability of this relaxation for a large class of submodular cost functions which we call value-monotone submodular functions. For special graph classes we give optimal algorithms.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
José R. Correa, Nicole Megow,