# Primal-dual approximation algorithms for a packing-covering pair of problems

Sofia Kovaleva; Frits C. R. Spieksma

RAIRO - Operations Research - Recherche Opérationnelle (2002)

- Volume: 36, Issue: 1, page 53-71
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topKovaleva, Sofia, and Spieksma, Frits C. R.. "Primal-dual approximation algorithms for a packing-covering pair of problems." RAIRO - Operations Research - Recherche Opérationnelle 36.1 (2002): 53-71. <http://eudml.org/doc/245768>.

@article{Kovaleva2002,

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

author = {Kovaleva, Sofia, Spieksma, Frits C. R.},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {primal-dual; approximation algorithms; packing-covering; intervals},

language = {eng},

number = {1},

pages = {53-71},

publisher = {EDP-Sciences},

title = {Primal-dual approximation algorithms for a packing-covering pair of problems},

url = {http://eudml.org/doc/245768},

volume = {36},

year = {2002},

}

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

PB - EDP-Sciences

VL - 36

IS - 1

SP - 53

EP - 71

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

LA - eng

KW - primal-dual; approximation algorithms; packing-covering; intervals

UR - http://eudml.org/doc/245768

ER -

## References

top- [1] J. Aerts and E.J. Marinissen, Scan chain design for test time reduction in core-based ICs, in Proc. of the International Test Conference. Washington DC (1998).
- [2] S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and hardness of approximation problems, in Proc. of the 33rd IEEE Symposium on the Foundations of Computer Science (1992) 14-23. Zbl0977.68539
- [3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela and M. Protasi, Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties. Springer Verlag, Berlin (1999). Zbl0937.68002MR1734026
- [4] A. Bar–Noy, S. Guha, J. Naor and B. Schieber, Approximating the Throughput of Multiple Machines in Real-Time Scheduling. SIAM J. Comput. 31 (2001) 331-352. Zbl0994.68073
- [5] A. Bar–Noy, R. Bar–Yehuda, A. Freund, J. Naor and B. Schieber, A Unified Approach to Approximating Resource Allocation and Scheduling. J. ACM 48 (2001) 1069-1090. Zbl1323.68564
- [6] P. Berman and B. DasGupta, Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling. J. Combin. Optim. 4 (2000) 307-323. Zbl0991.90061MR1776667
- [7] T. Erlebach and F.C.R. Spieksma, 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). Zbl1044.68753
- [8] N. Garg, V.V. Vazirani and M. Yannakakis, Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica 18 (1997) 3-20. Zbl0873.68075MR1432026
- [9] M.X. Goemans and D.P. Williamson, 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).
- [10] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, San Diego, California (1980). Zbl0541.05054MR562306
- [11] D.S. Hochbaum, Approximation algorithms for NP-hard problems. PWC Publishing Company, Boston (1997). Zbl05899342
- [12] D.S. Hochbaum, 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] C.H. Papadimitriou, Computational Complexity. Addison-Wesley, Reading, Massachussets (1994). Zbl0833.68049MR1251285
- [14] F.C.R. Spieksma, On the approximability of an interval scheduling problem. J. Schedul. 2 (1999) 215-227. Zbl0938.90034MR1991780
- [15] D.P. Williamson, Course notes Primal-Dual methods, available at http://www.research.ibm.com/people/w/williamson/#Notes

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.