Wireless capacity with arbitrary gain matrix

作     者：Halldorsson, Magnus M. Mitra, Pradipta 

作者机构：Reykjavik Univ Sch Comp Sci ICE TCS IS-101 Reykjavik Iceland 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2014年第553卷第0期

页      面：57-63页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Icelandic Research Fund 

主　　题：Wireless networks SINR model Semi-definite programming 

摘      要：Given a set of wireless links, a fundamental problem is to find the largest subset that can transmit simultaneously, within the SINR model of interference. Significant progress on this problem has been made in recent years. In this note, we study the problem in the setting where we are given a fixed set of arbitrary powers each sender must use, and an arbitrary gain matrix defining how signals fade. This variation of the problem appears immune to most algorithmic approaches studied in the literature. Indeed it is very hard to approximate since it generalizes the max independent set problem. Here, we propose a simple semi-definite programming approach to the problem that yields constant factor approximation, if the optimal solution is strictly larger than half of the input size. (C) 2013 Published by Elsevier B.V.