Primal-dual approximation algorithms for a packing-covering pair of problems
Sofia Kovaleva; Frits C.R. Spieksma
RAIRO - Operations Research (2010)
- Volume: 36, Issue: 1, page 53-71
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topKovaleva, Sofia, and Spieksma, Frits C.R.. "Primal-dual approximation algorithms for a packing-covering pair of problems." RAIRO - Operations Research 36.1 (2010): 53-71. <http://eudml.org/doc/105261>.
@article{Kovaleva2010,
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 + ε)-approximation algorithm for
the covering problem. Finally, we show that, unless
P = 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},
keywords = {Primal-dual; approximation algorithms; packing-covering; intervals.; primal-dual; intervals},
language = {eng},
month = {3},
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/105261},
volume = {36},
year = {2010},
}
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
DA - 2010/3//
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 + ε)-approximation algorithm for
the covering problem. Finally, we show that, unless
P = NP, the covering problem cannot be approximated in
polynomial time within arbitrarily good precision.
LA - eng
KW - Primal-dual; approximation algorithms; packing-covering; intervals.; primal-dual; intervals
UR - http://eudml.org/doc/105261
ER -
References
top- 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).
- 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.
- 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).
- 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.
- A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor and B. Schieber, A Unified Approach to Approximating Resource Allocation and Scheduling. J. ACM48 (2001) 1069-1090.
- P. Berman and B. DasGupta, Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling. J. Combin. Optim.4 (2000) 307-323.
- 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).
- N. Garg, V.V. Vazirani and M. Yannakakis, Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica18 (1997) 3-20.
- 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).
- M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, San Diego, California (1980).
- D.S. Hochbaum, Approximation algorithms for NP-hard problems. PWC PublishingCompany, Boston (1997).
- 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).
- C.H. Papadimitriou, Computational Complexity. Addison-Wesley, Reading, Massachussets (1994).
- F.C.R. Spieksma, On the approximability of an interval scheduling problem. J. Schedul.2 (1999) 215-227.
- D.P. Williamson, Course notes Primal-Dual methods, available at URIhttp://www.research.ibm.com/people/w/williamson/#Notes
NotesEmbed ?
topYou 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.