On Chromatic Sums and Distributed Resource Allocation

Amotz Bar-Noy*, Mihir Bellare, Magnús M. Halldórsson, Hadas Shachnai, Tami Tamir

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

123 Citations (Scopus)

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ρ-approximation of MCS for classes of graphs for which the maximum independent set problem can be approximated within a factor of ρ. On the other hand, we show that an n1 - ∈-approximation is NP-hard, for some ∈ > 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(log2 n) communication rounds.

Original languageEnglish
Pages (from-to)183-202
Number of pages20
JournalInformation and Computation
Volume140
Issue number2
DOIs
Publication statusPublished - 1 Feb 1998

Other keywords

  • Distributed resource allocation
  • Graph coloring
  • Maximum independent sets
  • Response time

Fingerprint

Dive into the research topics of 'On Chromatic Sums and Distributed Resource Allocation'. Together they form a unique fingerprint.

Cite this