Geodesic
Primal-dual approximation algorithms for a packing-covering pair of problems
RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 1, pp. 53-71

Voir la notice de l'article provenant de la source Numdam

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 𝒫=𝒩𝒫, the covering problem cannot be approximated in polynomial time within arbitrarily good precision.

DOI : 10.1051/ro:2002005
Classification : 05A05
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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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, Tome 36 (2002) no. 1, pp. 53-71. doi: 10.1051/ro:2002005

Cité par Sources :