Groupe d’études et de recherche en analyse des décisions

G-2000-09

Lower Bounds from Tile Covers for the Channel Assignment Problem

et

A method to generate lower bounds for the channel assignment problem is given. The method is based on the reduction of the channel assignment problem to a problem of covering the demand in a cellular network by pre-assigned blocks of cells, called tiles. This tile cover approach is applied to networks with a cosite constraint and two different constraints between cells. New bounds are derived using this method, which lead to improved results when applied to an example from the literature.

, 25 pages