|M.Sc Student||Polevoy Gleb|
|Subject||Bandwidth Allocation in Cellular Networks with Multiple|
|Department||Department of Computer Science||Supervisor||Professor Reuven Bar-Yehuda|
|Full Thesis text|
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 S that satisfies the following conditions:
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.