A combinatorial problem in which colors have to be assigned to intervals in such a way that two overlapping intervals are colored differently and the minimum number of colors is used. Such a problem corresponds to color the vertices of an interval graph, that is, a graph representing the intersections of the set of intervals.
Published in Chapter:
Scalable Algorithms for Server Allocation in Infostations
Alan A. Bertossi (University of Bologna, Italy), M. Cristina Pinotti (University of Perugia, Italy), and Phalguni Gupta (University of Udine, Italy)
Copyright: © 2010
|Pages: 12
DOI: 10.4018/978-1-60566-661-7.ch027
Abstract
The server allocation problem arises in isolated infostations, where mobile users going through the coverage area require immediate high-bit rate communications such as web surfing, file transferring, voice messaging, email and fax. Given a set of service requests, each characterized by a temporal interval and a category, an integer k, and an integer hc for each category c, the problem consists in assigning a server to each request in such a way that at most k mutually simultaneous requests are assigned to the same server at the same time, out of which at most hc are of category c, and the minimum number of servers is used. Since this problem is computationally intractable, a scalable 2-approximation online algorithm is exhibited. Generalizations of the problem are considered, which contain bin-packing, multiprocessor scheduling, and interval graph coloring as special cases, and admit scalable on-line algorithms providing constant approximations.