On Some Bounds on the Optimum Schedule Length in the SINR Model

摘要

In this paper the problem of wireless transmissions scheduling in the path-loss/SINR model is considered for different fixed power schemes. The lower bounds for the optimum schedule length proven by Kesselheim and Voecking are considered. It is shown that the lower bound for the linear power scheme is tight, by presenting a constant-factor approximation algorithm. On the other hand, it is shown that the lower bounds proven for many other interesting power schemes can be essentially far from the optima.