Interference in Cellular Networks: The Minimum Membership Set Cover Problem
The infrastructure for mobile distributed tasks is often formed by cellular networks. One of the major issues in such networks is interference. In this paper we tackle interference reduction by suitable assignment of transmission power levels to base stations. This task is formalized introducing the Minimum Membership Set Cover combinatorial optimization problem. On the one h and we prove that in polynomial time the optimal solution of the problem cannot be approximated more closely than with a factor In n. On the other h and we present an algorithm exploiting linear programming relaxation techniques which asymptotically matches this lower bound.
Fabian Kuhn Pascal von Rickenbach Roger Wattenhofer Emo Welzl Aaron Zollinger
Computer Engineering and Networks Laboratory, ETH Zurich, 8092 Zurich, Switzerland Department of Computer Science, ETH Zurich, 8092 Zurich, Switzerland
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
188-198
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）