### On chromatic sums and
distributed resource allocation

** Authors:** * A. Bar-Noy, M. Bellare, M. Halldorsson, H. Shachnai and
T. Tamir*
** Abstract: ** 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 (E. Kubicka and A. J. Schwenk, 1989. An introduction to chromatic
sums, in ``Proceedings of the ACM Computer Science Conference,'' pp.
39-45.). 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 4\rho-approximation
of MCS for classes of graphs for which the maximum independent set problem can
be approximated within a factor of \rho. On the other hand, we show that an
n^{1-\epsilon}-approximation is NP-hard, for some \epsilon > 0. For some
instances 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 obtained
distributively using compact coloring within O(log^2 n) communication rounds.

** Ref:** * Information and Computation*,
Vol. 140, No. 2, February 1998, pp. 183--202. Paper available below.