An approximation algorithm for the general max-min resource sharing problem

We propose an approximation algorithm for, the general max-min resource sharing problem with M nonnegative concave constraints on a convex set B. The algorithm is based on a Lagrangian decomposition method and it uses a c-approximation algorithm (called approximate block solver) for a simpler maximization problem over the convex set B. We show that our algorithm achieves within iterations or calls to the approximate block solver a solution for the general max-min resource sharing problem with approximation ratio The algorithm is faster and simpler than the previous known approximation algorithms for the problem [12, 13] Research of the author was supported in part by EU Thematic Network APPOL, Approximation and Online Algorithms, IST-2001-30012, by EU Project CRESCCO, Critical Resource Sharing for Cooperation in Complex Systems, IST-2001-33135 and by DFG Project, Entwicklung und Analyse von Approximativen Algorithmen für Gemischte und Verallgemeinerte Packungs- und überdeckungsprobleme, JA 612/10-1. Part of this work was done while visiting the Department of Computer Science at ETH Zürich. An extended abstract of this paper appeared in SWAT 2004, Scandinavian Workshop on Algorithm Theory, LNCS 3111, 311–322.