Some approximation algorithms for the clique partition problem in weighted interval graphs
Interval graphs play important roles in analysis of DNA chains in Benzer [S. Benzer, On the topology of the genetic fine structure, Proceedings of the National Academy of Sciences of the United States of America 45 (1959) 1607-1620], restriction maps of DNA in Waterman and Griggs [M.S. Waterman, J.R. Griggs, Interval graphs and maps of DNA, Bulletin of Mathematical Biology 48 (2) (1986) 189-195] and other related areas. In this paper, we study a new combinatorial optimization problem, named the minimum clique partition problem with constrained bounds, in weighted interval graphs. For a weighted interval graph G and a bound B, partition the weighted intervals of this graph G into the smallest number of cliques, such that each clique, consisting of some intervals whose intersection on a real line is not empty, has its weight not beyond B. We obtain the following results: (1) this problem is NP-hard in a strong sense, and it cannot be approximated within a factor 3/2 - epsilon in polynomial time for any epsilon > 0; (2) we design three approximation algorithms with different constant factors for this problem; (3) for the version where all intervals have the same weights, we design an optimal algorithm to solve the problem in linear time. (c) 2007 Elsevier B.V. All rights reserved.
approximation algorithms cliques weighted interval graphs