|
|
||
|
IMADA - Department of Mathematics and Computer Science |
|
Multi-coloring on the path is a model for frequency assignment in linear cellular networks. Issues of limited frequency reallocation as well as dynamic behavior allowing cancellation have been studied for hexagonal grids. We study these issues with respect to linear cellular networks. We completely close this problem by giving matching upper and lower bounds, both when the problem is static and when its dynamic and local recoloring may be permitted. In all cases, we show that randomization does not help. In addition, we give an exact characterization of the natural greedy algorithms for these problems. All of these results are with regard to competitive analysis. Taking steps towards a more fine-grained analysis, we prove that for the static case, even though randomization cannot bring the competitive ratio down to one, it seems that the greedy algorithm is expected optimal on uniform random request sequences. We prove this for small paths and indicate it experimentally for larger graphs. Host: SDU HOME | IMADA HOME | Previous Page Daniel Merkle |