The Taub Faculty of Computer Science Events and Talks

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.