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

Abstract

top
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.

How to cite

top

Kovaleva, 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [10] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, San Diego, California (1980). Zbl0541.05054MR562306
  11. [11] D.S. Hochbaum, Approximation algorithms for NP-hard problems. PWC Publishing Company, Boston (1997). Zbl05899342
  12. [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. [13] C.H. Papadimitriou, Computational Complexity. Addison-Wesley, Reading, Massachussets (1994). Zbl0833.68049MR1251285
  14. [14] F.C.R. Spieksma, On the approximability of an interval scheduling problem. J. Schedul. 2 (1999) 215-227. Zbl0938.90034MR1991780
  15. [15] D.P. Williamson, Course notes Primal-Dual methods, available at http://www.research.ibm.com/people/w/williamson/#Notes 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.