Lehrstuhl Mathematik & InformatikApproximation Algorithms for Channel Assignment in Cellular Radio Networks
Abstract. A radiocommunication system has to satisfy the channel requests in its service area subject to the constraints that the number of channels is limited and co-channel interference must be excluded. This paper explores the possibility of finding optimal or nearly optimal channel assignments in polynomial time. It relates this problem to 'graph-coloring' and, if the network is assumed as cellular, to 'packing in the plane'. an approximation algorithm is designed which satisfies at least a fraction of 1-e-1 of the maximum number of satisfiable requests. Several related versions of the problem are also analyzed. For some of them, approximation schemes are discovered. Finally, NP-completeness is shown for a very restricted version and lower bounds for the best performance ratios are discussed (under the P \neq NP-assumption).