Journal article
Max-Coloring and Online Coloring with Bandwidths on Interval Graphs
ACM transactions on algorithms, Vol.7(3), pp.1-21
07/01/2011
DOI: 10.1145/1978782.1978790
Abstract
Given a graph G = (V, E) and positive integral vertex weights w : V -> N, the max-coloring problem seeks to find a proper vertex coloring of G whose color classes C-1, C-2,C- ... , C-k, minimize Sigma(k)(i=1) max(v epsilon Ci) w(v). This problem, restricted to interval graphs, arises whenever there is a need to design dedicated memory managers that provide better performance than the general-purpose memory management of the operating system.
Though this problem seems similar to the dynamic storage allocation problem, there are fundamental differences. We make a connection between max-coloring and online graph coloring and use this to devise a simple 2-approximation algorithm for max-coloring on interval graphs. We also show that a simple first-fit strategy, that is a natural choice for this problem, yields an 8-approximation algorithm. We show this result by proving that the first-fit algorithm for online coloring an interval graph G uses no more than 8 . chi(G) colors, significantly improving the bound of 26 . chi(G) by Kierstead and Qin [1995]. We also show that the max-coloring problem is NP-hard.
The problem of online coloring of intervals with bandwidths is a simultaneous generalization of online interval coloring and online bin packing. The input is a set I of intervals, each interval i epsilon I having an associated bandwidth b(i) epsilon (0, 1]. We seek an online algorithm that produces a coloring of the intervals such that for any color c and any real r, the sum of the bandwidths of intervals containing r and colored c is at most 1. Motivated by resource allocation problems, Adamy and Erlebach [2003] consider this problem and present an algorithm that uses at most 195 times the number of colors used by an optimal offline algorithm. Using the new analysis of first-fit coloring of interval graphs, we show that the Adamy-Erlebach algorithm is 35-competitive. Finally, we generalize the Adamy-Erlebach algorithm to a class of algorithms and show that a different instance from this class is 30-competitive.
Details
- Title: Subtitle
- Max-Coloring and Online Coloring with Bandwidths on Interval Graphs
- Creators
- Sriram V. Pemmaraju - University of IowaRajiv Raman - Max Planck SocietyKasturi Varadarajan - University of Iowa
- Resource Type
- Journal article
- Publication Details
- ACM transactions on algorithms, Vol.7(3), pp.1-21
- Publisher
- Assoc Computing Machinery
- DOI
- 10.1145/1978782.1978790
- ISSN
- 1549-6325
- eISSN
- 1549-6333
- Number of pages
- 21
- Grant note
- DMS-0213305; CCR-0237431 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 07/01/2011
- Academic Unit
- Computer Science
- Record Identifier
- 9984259499602771
Metrics
9 Record Views