Approximation algorithms for covering/packing integer programs |
| |
Authors: | Stavros G Kolliopoulos |
| |
Affiliation: | a Department of Informatics and Telecommunications, National and Kapodistrain University of Athens, Panepistimiopolis Ilissia, Athens 157 84, Greece b Department of Computer Science and Engineering, University of California, Riverside, CA 92521, USA |
| |
Abstract: | Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing . We give a bicriteria-approximation algorithm that, given ε∈(0,1], finds a solution of cost O(ln(m)/ε2) times optimal, meeting the covering constraints (Ax?a) and multiplicity constraints (x?d), and satisfying Bx?(1+ε)b+β, where β is the vector of row sums βi=∑jBij. Here m denotes the number of rows of A.This gives an O(lnm)-approximation algorithm for CIP—minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx?b. The previous best approximation ratio has been O(ln(maxj∑iAij)) since 1982. CIP contains the set cover problem as a special case, so O(lnm)-approximation is the best possible unless P=NP. |
| |
Keywords: | Covering/packing integer programs Set cover Approximation algorithms Multiplicity constraints |
本文献已被 ScienceDirect 等数据库收录! |
|