Article ID: | iaor20052749 |
Country: | France |
Volume: | 36 |
Issue: | 1 |
Start Page Number: | 53 |
End Page Number: | 71 |
Publication Date: | Jan 2002 |
Journal: | RAIRO Operations Research |
Authors: | Spieksma Frits C.R., Kovaleva Sofia |
Keywords: | programming: linear |
We consider a special packing–covering pair of problems. The packing problem is a natural generalization of finding a (weighted) maximum independent set in an interval graph, the covering problem generalizes the problem of finding a (weighted) minimum clique cover in an interval graph. The problem pair involves weights and capacities; we consider the case of unit weights and the case of unit capacities. In each case we describe a simple algorithm that outputs a solution to the packing problem and to the covering problem that are within a factor of 2 of each other. Each of these results implies an approximative min–max result. For the general case of arbitrary weights and capacities we describe an LP-based (2+ε)-approximation algorithm for the covering problem. Finally, we show that, unless