Approximation Algorithms for Some Graph Partitioning Problems

This paper considers problems of the following type: given an edge-weighted k-colored input graph with maximum color class size c, find a minimum or maximum c-way cut such that each color class is totally partitioned. Equivalently, given a weighted complete k-partite graph, cover its vertices with a minimum number of disjoint cliques in such a way that the total weight of the cliques is maximized or minimized. Our study was motivated by some work called the index domain alignment problem [6], which shows its relevance to optimization of distributed computation. Solutions of these problems also have applications in logistics [3] and manufacturing systems [10]. In this paper, we design some approximation algorithms by extending the matching algorithms to these problems. Both theoretical and experimental results show that the algorithms we designed produce good approximations.