Directed weighted improper coloring for cellular channel allocation

Given a directed graph with weights on the vertices and on the arcs, a θθ-improper kk-coloring is an assignment of at most kk different colors to the vertices of GG such that the weight of every vertex vv is greater, by a given factor 1θ, than the sum of the weights on the arcs (u,v)(u,v) entering vv with the tail uu of the same color as vv. For a given real number θθ, we consider the problem of determining the minimum integer kk such that GG has a θθ-improper kk-coloring. Also, for a given integer kk, we consider the problem of determining the minimum real number θθ such that GG has a θθ-improper kk-coloring. We show that these two problems can be used to model channel allocation problems in wireless communication networks, when it is required that the power of the signal received at a base station is greater, by a given factor, than the sum of interfering powers received from mobiles which are assigned the same channel. We propose set partitioning formulations for both problems and describe branch-and-price algorithms to solve them. Computational experiments are reported for instances having a similar structure as real channel allocation problems.