Approximation Algorithms for Mixed Fractional Packing and Covering Problems

摘要

We study general mixed fractional packing and covering problems (MPC_ε) of the following form: Given a vector f : B → IR_+~M of M nonnegative continuous convex functions and a vector g : B → IR_+~M of M nonnegative continuous concave functions, two M - dimensional nonnegative vectors a, b, a nonempty convex compact set B and a relative tolerance ε ∈ (0, 1), find an approximately feasible vector x ∈ B such that f(x) ≤ (1 + ε)a and g(x) ≥ (1 — ε)b or find a proof that no vector is feasible (that satisfies x ∈ B, f(x) ≤ a and g(x) ≥ b). The fractional packing problem with convex constraints, i.e. to find x ∈ B such that f(x) ≤ (1 + ε)a, is solved in [4,5,8] by the Lagrangian decomposition method in O(M(ε~(-2) + ln M)) iterations where each iteration requires a call to an approximate block solver ABS(p, t) of the form: find x e B such that p~Tf(x) ≤ (1 + t)Λ(p) where Λ(p) = min_(x ∈ B)p~T f(x). Furthermore, Grigoriadis et al. [6] proposed also an approximation algorithm for the fractional covering problem with concave constraints, i.e. to find x ∈ B such that g(x) ≥ (1 — ε)b, within O(M(ε~(-2) + lnM)) iterations where each iteration requires here a call to an approximate block solver ABS(q, t) of the form: find x ∈ B such that q~Tg(x) ≥ (1 — t)Λ(q) where Λ(q) = max_(x ∈ B) q~T g(x). Both algorithms solve also the corresponding min-max and max-min optimization variants within the same number of iterations. Furthermore, the algorithms can be generalized to the case where the block solver has arbitrary approximation ratio [7,8,9].