Approximation of a geometric set covering problem

We consider a special set covering problem. This problem is a generalization of finding a minimum clique cover in an interval graph. When formulated as an integer program, the 0-1 constraint matrix of this integer program can be partitioned into an interval matrix and a special 0-1 matrix with a single I per column. We show that the value of this formulation is bounded by (2k)/(k+1) times the value of the LP-relaxation, where k is the maximum row sum of the special matrix. For the "smallest" difficult case, i.e., k = 2, this bound is tight. Also we provide an O(n) (3)/(2)-approximation algorithm in case k = 2.