Gleb Polevoy, M.Sc. Thesis Seminar
Wednesday, 22.12.2010, 14:00
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
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.