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⊆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 are vectors whose components are M non-negative convex and concave functions, respectively, and are constant positive vectors. Our algorithm requires an efficient feasibility oracle or block solver which, given vectors and α∈R+, computes such that or correctly decides that no such 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.