On coverage in infrastructure networks
Fabian Kühn, von Rickenbach, Pascal, Wattenhofer, Roger, Welzl, Emo, Zollinger, Aaron · Repository for Publications and Research Data (ETH Zurich) · 2004
For mobile distributed tasks, the infrastructure 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 hand we prove that in polynomial time the optimal solution of the problem cannot be approximated more closely than with a factor ln n. On the other hand we present an algorithm exploiting linear programming relaxation techniques which not only asymptotically matches the lower bound with high probability but also performs well in practical networks.