Clique partitioning with value-monotone submodular cost |
| |
Institution: | 1. Departamento Ingeniería Industrial, Universidad de Chile, Santiago, Chile;2. Department of Mathematics, Technische Universität Berlin, Germany |
| |
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. |
| |
Keywords: | Partition into cliques Cost coloring Submodular functions Cardinality constraint Max-coloring Batch-scheduling with compatibilities |
本文献已被 ScienceDirect 等数据库收录! |