Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Bandwidth Allocation in Cellular Networks with Multiple Interferences
event speaker icon
Gleb Polevoy (M.Sc. Thesis Seminar)
event date icon
Wednesday, 22.12.2010, 14:00
event location icon
Taub 601
event speaker icon
Advisor: Prof. R. Bar-Yehuda
We study the problem of bandwidth allocation with multiple interferences. In this problem the input consists of a set of users and a set of base stations. Each user has a list of requests, each consisting of a base station, a frequency demand, and a profit that may be gained by scheduling this request. The goal is to find a maximum profit set of user requests $\calS$ that satisfies the following conditions: 1) $\calS$ contains at most one request per user, 2) the frequency sets allotted to requests in $\calS$ that correspond to the same base station are pairwise non-intersecting, and 3) the QoS received by any user at any frequency is reasonable according to an interference model. We show that these problems are extremely hard to approximate if the interferences depend on both the interfered and the interfering base stations. On the other hand, we provide constant factor approximation algorithms for the case where the interferences depend only on the interfering base stations. We employ the local ration technique. We also consider a restrictive special case that is closely related to the knapsack problem. We show that this special case is NP-hard and that it admits an FPTAS.