On the Problem of Wireless Scheduling With Linear Power Levels - Tonoyan, Tigran (Mathematical Problems of Computer Science, 2021)
In this work we consider the problem of communication scheduling in wireless networks with respect to the SINR (Signal to Interference plus Noise Ratio) constraint in metric spaces. For the powers of sender nodes we consider the linear power assignment, which is one of commonly considered power schemes. We give a constant factor deterministic approximation algorithm for scheduling in wireless networks, which are given in some special class of metric spaces, which contains the Euclidean spaces. To the best of our knowledge, this is the first constant factor approximation algorithm for this problem. Simultaneously we obtain the approximate value of the optimal schedule length with error at most a constant factor.