Approximation algorithms for channel assignment with constraints

Cellular networks are generally modeled as node-weighted graphs, where the nodes represent cells and the edges represent the possibility of radio inte rference. An algorithm for the channel assignment problem must assign as ma ny channels as the weight indicates to every node, such that any two channe ls assigned to the same node satisfy the co-site constraint, and any two ch annels assigned to adjacent nodes satisfy the inter-site constraint. We des cribe several approximation algorithms for channel assignment with arbitrar y co-site and inter-site constraints for odd cycles and the so-called hexag on graphs that are often used to model cellular networks. The algorithms gi ven for odd cycles are optimal for some values of constraints, and have per formance ratio at most 1 + 1/(n - 1) for all other cases, where n is the le ngth of the cycle. Our main result is an algorithm of performance ratio at most 4/3 + 1/100 for hexagon graphs with arbitrary co-site and inter-site c onstraints. (C) 2001 Elsevier Science B.V. All rights reserved.