On Chromatic Sums and Distributed Resource Allocation

This paper studies an optimization problem that arises in the context of distributed resource allocation: Given a conflict graph that represents the competition of processors over resources, we seek an allocation under which no two jobs with conflicting requirements are executed simultaneously. Our objective is to minimize the average response time of the system. In alternative formulation this is known as the Minimum Color Sum (MCS) problem [24]. We show, that the algorithm based on finding iteratively a maximum independent set (MaxIS) is a 4-approximation to the MCS. This bound is tight to within a factor of 2. We give improved ratios for the classes of bipartite, bounded-degree, and line graphs. The bound generalizes to a 4ae-approximation of MCS for classes of graphs for which the maximum independent set problem can be approximated within a factor of ae. On the other hand, we show that an n 1\Gammaffl -approximation is NP-hard, for some ffl ? 0. For some instances of the resource..