APPROXIMATION ALGORITHMS FOR MIXED FRACTIONAL PACKING AND COVERING PROBLEMS

摘要

We propose an approximation algorithm based on the Lagrangian or price -directive decomposition method to compute an ε-approximate solution of the mixed fractional packing and covering problem: find x ∈ B such that f(x) ≤ (1 + ε)a, g(x) ≥ (1 - ?)b where f(x),g(x) are vectors with M nonnegative convex and concave functions, a and 6 are M - dimensional nonnegative vectors and B is a convex set that can be queried by an optimization or feasibility oracle. We propose an algorithm that needs only O(Mε~(-2) ln(Mε~(-1))) iterations or calls to the oracle. The main contribution is that the algorithm solves the general mixed fractional packing and covering problem (in contrast to pure fractional packing and covering problems and to the special mixed packing and covering problem with B = IR_+~N and runs in time independent of the so-called width of the problem.