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

作     者：Kovaleva, S Spieksma, FCR 

作者机构：Maastricht Univ Dept Math NL-6200 MD Maastricht Netherlands Katholieke Univ Leuven Dept Appl Econ B-3000 Louvain Belgium 

出 版 物：《RAIRO-OPERATIONS RESEARCH》 (法国自动化、信息与运筹学；运筹学)

年 卷 期：2002年第36卷第1期

页      面：53-71页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主　　题：primal-dual approximation algorithms packing-covering intervals 

摘      要：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 P = NP, the covering problem cannot be approximated in polynomial time within arbitrarily good precision.