This paper studies an optimization problem that arises in the context
of distributed resource allocation: Given a conflict graph that repres
ents the competition of processors over resources, we seek an allocati
on 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 Minimu
m Color Sum (MCS) problem (E. Kubicka and A. J. Schwenk, 1989. An intr
oduction to chromatic sums, in ''Proceedings of the ACM Computer Scien
ce Conference,'' pp. 39-45.). We show that the algorithm based on find
ing 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 impr
oved ratios for the classes of bipartite, bounded-degree, and line gra
phs. The bound generalizes to a 4p-approximation of MCS for classes of
graphs for which the maximum independent set problem can be approxima
ted within a factor of rho. On the other hand, we show that an n(1-eps
ilon)-approximation is NP-hard, for some epsilon > 0. For some instanc
es of the resource allocation problem, such as the Dining Philosophers
, an efficient solution requires edge coloring of the conflict graph.
We introduce the Minimum Edge Color Sum (MECS) problem which is shown
to be NP-hard. We show that a 2-approximation to MECS(G) can be obtain
ed distributively using compact coloring within O(log(2) n) communicat
ion rounds. (C) 1998 Academic Press.