| TR#: | MSC-2011-05 |
| Class: | MSC |
| Title: | Bandwidth Allocation in Cellular Neworks with Multiple Interference |
| Authors: | Gleb Polevoy |
| Supervisors: | Reuven Bar-Yehuda |
| MSC-2011-05.pdf | |
| Abstract: | 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:
1) S contains at most one request per user, 2) the frequency sets allotted to requests in S 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 consider two variants of bandwidth allocation with multiple interferences. In the first each request specifies a demand that can be satisfied by any subset of frequencies that is large enough. In the second each request specifies a specific frequency interval. Furthermore, we consider two interference models, multiplicative and additive. 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 both variants of bandwidth allocation with multiple interferences 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. The FPTAS uses a dynamic programming approach. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2011/MSC/MSC-2011-05), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the MSC technical reports of 2011
To the main CS technical reports page