Approximation algorithms for the fractional covering problem, and applications

We generalize a method by Grigoriadis et al. to compute an

approximate solution of the fractional covering (and max-min

resource sharing) problem with M nonnegative linear (or concave)

constraints on a convex set B to the case with general

approximate block solvers (i.e. with only constant, logarithmic,

or even worse approximation ratios). The algorithm is based on a

Lagrangian decomposition which uses a modified logarithmic potential

function and on several other ideas (scaling phase strategy, two

stopping rules in a phase, eliminating functions larger than

a threshold value T, reducing the step length and taking a convex

combination among different iterates in a phase). We show that the

algorithm runs in iterations

(or block optimization steps), a data and approximation ratio

independent bound which is optimal up to poly-logarithmic factors for

any fixed relative accuracy epsilon in (0,1). Furthermore, we

show how to apply this method for serveral applications (preemptive

resource constrained scheduling, scheduling malleable tasks, and

fractional weighted graph coloring).