The on-line first-fit algorithm for radio frequency assignment problems. (Q1853136)

The radio frequency assignment problem is to minimize the number of frequencies used by transmitters with no interference in radio communication networks; it can be modeled as the minimum vertex coloring problem on unit disk graphs. In this paper, we consider the on-line first-fit algorithm for the problem and show that the competitive ratio of the algorithm for the unit disk graph \(G\) with \(\chi(G)=2\) is 3, where \(\chi(G)\) is the chromatic number of \(G.\) Moreover, the competitive ratio of the algorithm for the unit disk graph \(G\) with \(\chi(G)>2\) is at least \(4-3/\chi(G)\). The average performance for the algorithm is also discussed in this paper.