We consider a special packing-covering pair of problems. Thepacking problem is a natural generalization of finding a(weighted) maximum independent set in an interval graph, thecovering problem generalizes the problem of finding a (weighted)minimum clique cover in an interval graph. The problem pairinvolves weights and capacities; we consider the case of unitweights and the case of unit capacities. In each case we describea simple algorithm that outputs a solution to the packing problemand to the covering problem that are within a factor of 2 of eachother. Each of these results implies an approximative min-maxresult. For the general case of arbitrary weights and capacitieswe describe an LP-based (2 + ε)-approximation algorithm forthe covering problem. Finally, we show that, unlessP = NP, the covering problem cannot be approximated inpolynomial time within arbitrarily good precision.
