On the clique partitioning problem in weighted interval graphs

The minimum clique partitioning problem in weighted interval graphs (MCPI) is defined as follows. Given an interval graph with nonnegative node weights, the problem is to partition the nodes into a set of cliques such that the sum of node weights in each clique is no more than a given bound. The objective of the problem is to minimize the number of cliques. Recently, Chen et al. [M. Chen, J. Li, J. Li, W. Li, and L. Wang, Some approximation algorithms for the clique partitioning problem in weighted interval graphs, Theoretical Computer Science 381 (2007), 124–133] proposed three approximation algorithms having constant factors 3, 2.5 and 2, and a linear time optimal algorithm for the case with identical weights. In this paper, we show that their factor 2 algorithm does not achieve the expected approximation ratio and the linear time algorithm cannot give an optimal solution for the identical weights case. We also develop an approximation algorithm with factor 2 for the variable weights case and an exact algorithm for the identical weights case.