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

Issue		RAIRO Oper. Res. Volume 36, Number 1, January-March 2002


Page(s)		53 - 71
DOI		10.1051/ro:2002005

RAIRO Oper. Res. 36 (2002) 53-71
DOI: 10.1051/ro:2002005

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

Sofia Kovaleva¹ and Frits C.R. Spieksma²

¹ Department of Mathematics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands; s.kovaleva@math.unimaas.nl.
² Department of Applied Economics, Katholieke Universiteit Leuven, Naamsestraat 69, 3000 Leuven, Belgium.

(Received December, 2000)

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 $\cal{P}=\cal{NP}$ , the covering problem cannot be approximated in polynomial time within arbitrarily good precision.

Mathematics Subject Classification. 05A05.

Key words: Primal-dual, approximation algorithms, packing-covering, intervals.

© EDP Sciences 2002

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.