MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTECardinality Constrained Graph Partitioning into Cliques with Submodular Costs
par Karol Suchan
| Date : | 02/02/10 | | Time : | 10:30 | | Location : | Lagrange Gris |
<pre>We consider the problem of partitioning a graph into cliques of bounded<br />cardinality. The goal is to find a partition that minimizes the sum of<br />clique costs, where the cost of a clique is given by a set function on the<br />nodes. We present a general algorithmic solution based on solving the<br />problem without the cardinality constraint. Our algorithm yields a<br />constant factor approximation depending on the solvability of this<br />relaxation for a large class of submodular functions. We give optimal<br />algorithms for special graph classes.<br /></pre>
Page des séminaires
| 
