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 f_m 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 f_m 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 O(Mepsilon^-2ln(Mepsilon^-1)) 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).