2011/11/22 by Magnús M. Halldórsson, Magnus M. Halldorsson, Halldorsson, Magnus M. +2
Computer Science · #Cognitive Radio Networks and Spectrum Sensing #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Wireless Communication Networks Research #cs.DS #cs.NI
paper · pdf · doi:10.48550/arxiv.1111.5200
to appear in INFOCOM 2012, 16 pages, 4 fgures
openalex publication_date 2011/11/22 · arxiv created 2012/01/19 · arxiv updated 2012/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give algorithms with constant-factor performance guarantees for several capacity and throughput problems in the SINR model. The algorithms are all based on a novel LP formulation for capacity problems. First, we give a new constant-factor approximation algorithm for selecting the maximum subset of links that can be scheduled simultaneously, under any non-decreasing and sublinear power assignment. For the case of uniform power, we extend this to the case of variable QoS requirements and link-dependent noise terms. Second, we approximate a problem related to cognitive radio: find a maximum set of links that can be simultaneously scheduled without affecting a given set of previously assigned links. Finally, we obtain constant-factor approximation of weighted capacity under linear power assignment.