Maximizing wireless network capacity with linear power: Breaking the logarithmic barrier

Maximizing the wireless network capacity under physical interference model is notoriously hard due to the non-locality and the additive nature of the wireless interference under the physical interference model. This problem has been extensively studied recently with the achievable approximation bounds progressively improved from the linear factor to logarithmic factor. It has been a major open problem whether there exists a constant-approximation approximation algorithm for maximizing the wireless network capacity under the physical interference model. In this paper, we improve the status quo for the case of linear transmission power assignment, which is widely adopted due to its advantage of energy conservation. By exploring and exploiting the rich nature of the wireless interference with the linear power assignment, we develop constant-approximation algorithms for maximizing the wireless network capacity with linear transmission power assignment under the physical interference model, in both the unidirectional mode and the bidirectional mode.