Wireless Publications

Magnus M. Halldorsson

Link Capacity and Scheduling

Effective Wireless Scheduling via Hypergraph Sketches (with Tigran Tonoyan). SICOMP, 2021.
Universal Framework for Wireless Scheduling Problems (with Tigran Tonoyan)
ICALP, to appear, July 2017. Received Best paper award at Track C. Invited to Highlights on Algorithms, June 2018.

Wireless Link Capacity under Shadowing and Fading (with Tigran Tonoyan). June 2017. In MobiHoc 2017.

The Power of Non-Uniform Wireless Power (with Stephan Holzer, Pradipta Mitra and Roger Wattenhofer)
SIAM Journal of Computing, 46(3):1062--1098, June 2017

The Price of Local Power Control in Wireless Scheduling (with Tigran Tonoyan).
FSTTCS'15, full version, Feb 2015.

Limitations of Current Wireless Scheduling Algorithms (with Tigran Tonoyan).
ALGOSENSORS'15 Part of arXiv:1502.05279

A Note on Vertex Coloring Edge-Weighted Digraphs (with Joergen Bang-Jensen)
Mittag-Leffler Report No. 29, 2013/2014, spring. Information Processing Letters, 115(10):791-796, October 2015.

How Well Can Graphs Represent Wireless Interference? (with Tigran Tonoyan)
STOC '15
Full version on arXiv

Progress (and Lack Thereof) for Graph Coloring Approximation Problems
SOFSEM'15 (invited paper), Jan 2015

Beyond Geometry : Towards Fully Realistic Wireless Models (with Marijke Bodlaender)
PODC'14

Algorithms for Wireless Capacity (with Olga Goussevskaia and Roger Wattenhofer).
IEEE/ACM Transactions on Networking, June 2014. A note on precedence and credit.
This paper incorporates (and corrects) the results in the two papers "Capacity of Arbitrary Wireless Networks" and "Wireless Communication is in APX".

Wireless capacity with arbitrary gain matrix (with Pradipta Mitra)
Theoretical Computer Science 553:57--63, October 2014. Preliminary version appears in ALGOSENSORS'11.

Wireless scheduling with power control
ACM Transactions on Algorithms, Dec 2013. Preliminary version appeared in ESA'09

The Power of Non-Uniform Wireless Power (with Stephan Holzer, Pradipta Mitra and Roger Wattenhofer)
SODA'13, full version

Wireless Capacity and Admission Control in Cognitive Radio (with Pradipta Mitra). arxiv.org/abs/1111.5200.
Infocom '12

Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model (with Pradipta Mitra).
Distributed Computing 29(2):77-88, 2016.
Earlier version appears in ICALP '11.

Wireless Capacity with Oblivious Power in General Metrics (with Pradipta Mitra).
In SODA '11

Wireless Communication is in APX (with Roger Wattenhofer).
ICALP, July 2009 Retraction

Capacity of Arbitrary Wireless Networks (with Olga Goussevskaia, Roger Wattenhofer, and Emo Welzl).
INFOCOM, April 2009 Note on precedence and credit.

Modeling Aspects and Evaluations

Wireless Link Capacity under Shadowing and Fading (with Tigran Tonoyan). June 2017.
In MobiHoc 2017.
Invited paper: Models for wireless algorithms.
WiOpt, May 2016.
Wireless Scheduling Algorithms in Complex Environments (with Helga Gudmundsdottir, Eyjo Asgeirsson, Marijke Bodlaender, Joe Foley and Ymir Vigfusson)
MSWiM'14

Beyond Geometry : Towards Fully Realistic Wireless Models (with Marijke Bodlaender)
PODC'14

Invited paper: Modeling Reality Algorithmically: The Case of Wireless Communication.
ALGOSENSORS, July 2013.

Distributed Algorithms

Leader election in SINR model with arbitrary power control (with Stephan Holzer, Evangelia Anna Markatou, and Nancy Lynch). TCS April 2020.
Leveraging multiple channels in ad hoc networks
Distributed Computing (with Yuexuan Wang and Dongxiao Yu), to appear. (earlier version)

Data Dissemination in Unified Dynamic Wireless Networks (with Tigran Tonoyan, Yuexuan Wang, Dongxiao Yu)
IPDPS, May 2017. (Full version)
Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks
PODC '16 (with Tigran Tonoyan, Yuexuan Wang, Dongxiao Yu)

Leveraging Multiple Channels in Ad Hoc Networks
PODC '15 (with Yuexuan Wang, Dongxiao Yu)

A Local Broadcast Layer for the SINR Network Model (with
PODC '15 (with Stephan Holzer, Nancy Lynch)
Full version on arXiv

Connectivity and aggregation in multihop wireless networks (with Marijke Bodlaender and Pradipta Mitra)
PODC'13

Towards Tight Bounds for Local Broadcasting (with Pradipta Mitra)
FOMC'12

Distributed Connectivity of Wireless Networks (with Pradipta Mitra)
PODC'12

Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model (with Pradipta Mitra).
Distributed Computing 29(2):77-88, 2016.
Earlier version appears in ICALP '11.

Connectivity and Aggregation

Wireless Aggregation at Nearly Constant Rate (with Tigran Tonoyan), Dec 2017. (Poster at MobiHoc 2017.

The Power of Non-Uniform Wireless Power (with Stephan Holzer, Pradipta Mitra and Roger Wattenhofer)
SIAM Journal of Computing, 46(3):1062--1098, June 2017

Connectivity and aggregation in multihop wireless networks (with Marijke Bodlaender and Pradipta Mitra)
PODC'13

The Power of Non-Uniform Wireless Power (with Stephan Holzer, Pradipta Mitra and Roger Wattenhofer)
SODA'13, full version

Distributed Connectivity of Wireless Networks (with Pradipta Mitra)
PODC'12

Wireless Connectivity and Capacity
SODA '12 (with Pradipta Mitra).

Stochastic Packet Scheduling and Throughput

Maximum MIMO Flow in wireless networks under the SINR model (with Eyjo Asgeirsson and Pradipta Mitra)
WiOPT'14

Wireless Network Stability in the SINR Model (with Eyjo Asgeirsson and Pradipta Mitra)
SIROCCO'12

A Fully Distributed Algorithm for Throughput Performance in Wireless Networks (with Eyjo Asgeirsson and Pradipta Mitra)
CISS'12

Older papers on wireless (or wireless-motivated) problems in graph-based models

Minimizing Interference of a Wireless Ad-Hoc Network in a Plane
Theoretical Computer Science, 2008 (with Takeshi Tokuyama). Earlier version appears in ALGOSENSORS '06

On Spectrum Sharing Games
PODC 2004 (with Joseph Y. Halpern, Li (Erran) Li, Vahab S. Mirrokni). Full version appears in Distributed Computing

Approximating the (h,k)-labelling problem.
Int. J. Mobile Mobile Network Design and Innovation 1(2):113--117, 2006.
Most recent papers are on arXiv.

Last revised 6 Dec 2016, Magnus M Halldorsson