Directed weighted improper coloring for cellular channel allocation

Given a directed graph with weights on the vertices and on the arcs, a θ-improper k-coloring is an assignment of at most k different colors to the vertices of G such that the weight of every vertex v is greater, by a given factor 1θ, than the sum of the weights on the arcs (u,v) entering v with the tail u of the same color as v. For a given real number θ, we consider the problem of determining the minimum integer k such that G has a θ-improper k-coloring. Also, for a given integer k, we consider the problem of determining the minimum real number θ such that G has a θ-improper k-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.