Improved approximation algorithms for the general max-min resource sharing and fractional covering problem

max-min resource sharing (and fractional covering) problem with
$M$ nonnegative concave (linear) constraints on a convex set $B$.
The algorithm (based on a Lagrangian decomposition method) uses an
approximate block solver that solves a simpler maximization
problem over the convex set $B$ (called the block problem)
approximately with ratio $c \ge 1$. We show that our algorithm
achieves within $O(M \epsilon^{-2} \ln (M \epsilon^{-1}))$
iterations or calls to the approximate block solver a solution for
the max-min resource sharing and fractional covering problem with
approximation ratio $c / (1 - \epsilon)$. Our algorithm is the
first one for both problems where the number of iterations is
independent of the input data and the approximation ratio $c$.
Furthermore we show how to use this algorithm for two interesting
applications (the preemptive resource constrained scheduling and
fractional weighted coloring problem). The underlying block
problems in these applications are the classical $(s+1)$ -
dimensional knapsack and weighted independent set problem,
respectively. For both applications we give approximation
algorithms with improved running times.