neal young / Kolliopoulos05Approximation

  • Png/JCSS_2005.png Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of minimizing c$\cdot$x subject to x$\in Z^n_+$, Ax ≥ a, Bx ≤ b, and x ≤ d. We give a bicriteria-approximation algorithm that, given ε$\in$(0, 1], finds a solution of cost O(log(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=$\sum_j$ Bij. Here m is the number of rows of A.

    This gives an O(log m)-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(log maxj $\sum_i$Aij since 1982. CIP contains the set cover problem as a special case, so O(log m)-approximation is the best possible unless P=NP.

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.