Improved Approximations for the Max k-Colored Clustering Problem

摘要

In the Max k-Colored Clustering Problem we are given an undirected graph G = (V, E). Each edge e of G has a nonnegative weight w(e) and a color c(e) ∈ C = {1,2,...,k}. It is required to assign a color from C to each vertex of G so as to maximize the total weight of edges whose both endpoints have the same color as the color of the edge. Angel et al. [1] show that the problem is strongly NP-hard and present a randomized constant-factor approximation algorithm for solving it. We improve this result in two directions. First, we give a more careful analysis of the algorithm in [1], which significantly improves on its approximation bound (0.25 instead of 1/e~2 ≈ 0.135). Second, we present a different algorithm with a better worst case performance guarantee of 7/23 ≈ 0.304. Both algorithms are based on using similar randomized rounding schemes for a natural LP relaxation of the problem. They can be derandomized in a standard way by computing conditional expectations for some estimate function.