 |
|
|||
| Authors: | Udo Adamy, Thomas Erlebach |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | Online Coloring of Intervals with Bandwidth |
| Year: | 2004 |
| Pub-Key: | AE03 |
| Book Titel: | Lecture Notes in Computer Science. Proceedings of the First Workshop on Approximation and Online Algorithms (WAOA 2003) |
| Volume: | 2909 |
| Pages: | 1-12 |
| Publisher: | Springer-Verlag |
| Abstract: | Motivated by resource allocation problems in communication networks, we consider the problem of online interval coloring in the case where the intervals have weights in [0,1] and the total weight of intersecting intervals with the same color must not exceed 1. We present an online algorithm for this problem that achieves a constant competitive ratio. Our algorithm is a combination of an optimal online algorithm for coloring interval graphs and First-Fit coloring, for which we generalize the analysis of Kierstead to the case of non-unit bandwidth. |
| Location: | Budapest, Hungary |
| Resources: | [BibTeX] |
