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+\u03f5)$-approximation algorithm for the covering problem. Finally, we show that, unless $\mathcal{P}=\mathrm{\mathcal{N}\mathcal{P}}$, the covering problem cannot be approximated in polynomial time within arbitrarily good precision.

Keywords: primal-dual, approximation algorithms, packing-covering, intervals

@article{RO_2002__36_1_53_0, author = {Kovaleva, Sofia and Spieksma, Frits C. R.}, title = {Primal-dual approximation algorithms for a packing-covering pair of problems}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {53--71}, publisher = {EDP-Sciences}, volume = {36}, number = {1}, year = {2002}, doi = {10.1051/ro:2002005}, mrnumber = {1920379}, zbl = {1027.90107}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro:2002005/} }

TY - JOUR AU - Kovaleva, Sofia AU - Spieksma, Frits C. R. TI - Primal-dual approximation algorithms for a packing-covering pair of problems JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2002 SP - 53 EP - 71 VL - 36 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2002005/ DO - 10.1051/ro:2002005 LA - en ID - RO_2002__36_1_53_0 ER -

%0 Journal Article %A Kovaleva, Sofia %A Spieksma, Frits C. R. %T Primal-dual approximation algorithms for a packing-covering pair of problems %J RAIRO - Operations Research - Recherche Opérationnelle %D 2002 %P 53-71 %V 36 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2002005/ %R 10.1051/ro:2002005 %G en %F RO_2002__36_1_53_0

Kovaleva, Sofia; Spieksma, Frits C. R. Primal-dual approximation algorithms for a packing-covering pair of problems. RAIRO - Operations Research - Recherche Opérationnelle, Volume 36 (2002) no. 1, pp. 53-71. doi : 10.1051/ro:2002005. http://www.numdam.org/articles/10.1051/ro:2002005/

[1] Scan chain design for test time reduction in core-based ICs, in Proc. of the International Test Conference. Washington DC (1998).

and ,[2] Proof verification and hardness of approximation problems, in Proc. of the 33rd IEEE Symposium on the Foundations of Computer Science (1992) 14-23. | Zbl

, , , and ,[3] Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties. Springer Verlag, Berlin (1999). | MR | Zbl

, , , , and ,[4] Approximating the Throughput of Multiple Machines in Real-Time Scheduling. SIAM J. Comput. 31 (2001) 331-352. | MR | Zbl

, , and ,[5] A Unified Approach to Approximating Resource Allocation and Scheduling. J. ACM 48 (2001) 1069-1090. | MR | Zbl

, , , and ,[6] Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling. J. Combin. Optim. 4 (2000) 307-323. | MR | Zbl

and ,[7] Simple algorithms for a weighted interval selection problem, in Proc. of the 11th Annual International Symposium on Algorithms and Computation (ISAAC '00). Lecture Notes in Comput. Sci. 1969 (2000) 228-240 (see also Report M00-01, Maastricht University). | MR | Zbl

and ,[8] Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica 18 (1997) 3-20. | MR | Zbl

, and ,[9] The primal-dual method for approximation algorithms and its application to network design problems, Chap. 4 of Approximation algorithms for NP-hard problems, edited by D.S. Hochbaum. PWC Publishing Company, Boston (1997).

and ,[10] Algorithmic Graph Theory and Perfect Graphs. Academic Press, San Diego, California (1980). | MR | Zbl

,[11] Approximation algorithms for NP-hard problems. PWC Publishing Company, Boston (1997).

,[12] Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set and Related Problems, Chap. 3 of Approximation algorithms for NP-hard problems, edited by D.S. Hochbaum. PWC Publishing Company, Boston (1997).

,[13] Computational Complexity. Addison-Wesley, Reading, Massachussets (1994). | MR | Zbl

,[14] On the approximability of an interval scheduling problem. J. Schedul. 2 (1999) 215-227. | MR | Zbl

,[15] Course notes Primal-Dual methods, available at http://www.research.ibm.com/people/w/williamson/#Notes

,*Cited by Sources: *