Clique Partitioning with Value-monotone Submodular Cost

Correa, José R.; Megow, Nicole

doi:10.1016/j.disopt.2014.11.001

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Clique Partitioning with Value-monotone Submodular Cost

MPS-Authors

/persons/resource/persons45020

Megow, Nicole
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Correa, J. R., & Megow, N. (2015). Clique Partitioning with Value-monotone Submodular Cost. Discrete Optimization, 15, 26-36. doi:10.1016/j.disopt.2014.11.001.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-4E79-5

Abstract

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.