Faster and simpler approximation algorithms for mixed packing and covering problems

摘要

We propose an algorithm for approximately solving the mixed packing and covering problem; given a convex compact set 0≠B C RN, either compute x∈B such that f(x)≤(1+)a and g(x)≥(1-ε)b or decide that {x∈B|f(x)≤a,g(x)≥b}=0. Here f,g: B→R+M are vectors whose components are M non-negative convex and concave functions, respectively, and a,b ∈R++M are constant positive vectors. Our algorithm requires an efficient feasibility oracle or block solver which, given vectors c,d ∈ R+M and α∈R+, computes x∈B such that cTf(x)-dTg(x)≤α or correctly decides that no such x∈B exists. Our algorithm, which is based on the Lagrangian or price-directive decomposition method, generalizes the result from [K. Jansen, Approximation algorithm for the mixed fractional packing and covering problem, in: Proceedings of 3rd IFIP Conference on Theoretical Computer Science, IFIP TCS 2004, Kluwer, 2004, pp. 223–236; SIAM Journal on Optimization 17 (2006) 331–352] and needs only O(M(lnM+ε-2lnε-1)) iterations or calls to the feasibility oracle. Furthermore we show that a more general block solver can be used to obtain a more general approximation within the same runtime bound.