von Rickenbach, Pascal
Rights / licenseIn Copyright - Non-Commercial Use Permitted
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. Show more
Journal / seriesTechnical report
PublisherETH, Department of Computer Science
SubjectCellular networks; NETZWERKÜBERWACHUNG + NETZWERKADMINISTRATION (COMPUTERSYSTEME); Linear programming relaxation; Combinatorial optimization; Approximation algorithms; NETWORK MONITORING (COMPUTER SYSTEMS); Interference
Organisational unit02150 - Dep. Informatik / Dep. of Computer Science
NotesTechnical Reports D-INFK.
Weitere Autoren: Emo Welzl, Aaron Zollinger.
MoreShow all metadata