The power of non-uniform wireless power

Magnús M. Halldórsson*, Stephan Holzer, Pradipta Mitra, Roger Wattenhofer

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

26 Citations (Scopus)


We study a fundamental measure for wireless interference in the SINR model known as (weighted) inductive independence. This measure characterizes the effectiveness of using oblivious power - when the power used by a transmitter only depends on the distance to the receiver - as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves - due to existing lower bounds - capacity that is asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems for oblivious power and for power control, including distributed scheduling, connectivity, secondary spectrum auctions, and dynamic packet scheduling.

Original languageEnglish
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
PublisherAssociation for Computing Machinery, Inc
Number of pages12
ISBN (Print)9781611972511
Publication statusPublished - 2013
Event24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States
Duration: 6 Jan 20138 Jan 2013

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Conference24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Country/TerritoryUnited States
CityNew Orleans, LA


Dive into the research topics of 'The power of non-uniform wireless power'. Together they form a unique fingerprint.

Cite this