Lower bounds from tile covers for the channel assignment problem


Jeannette C.M. Janssen
Tania E. Wentzell
Shannon L. Fitzpatrick

Author Addresses: 

Jeannette Janssen (janssen@mathstat.dal.ca)
Tania Wentzell (tania@mathstat.dal.ca)
Dept. of Mathematics and Statistics
Dalhousie University
B3H 3J5 Halifax, NS

Shannon Fitzpatrick (slfitzpatric@upei.ca)
Dept. of Mathematics and Computer Science
University of Prince Eward Island
C1A 4P3 Charlottetown, PEI


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 co-site constraint and two different constraints between cells. A complete family of lower bounds is obtained which include a number of new bounds, and improve or include almost all known clique bounds. When applied to an example from the literature, the new bounds give better results.

Tech Report Number: 
Report Date: 
May 1, 2003
PDF icon CS-2003-05.pdf475.44 KB