---
_id: '17658'
abstract:
- lang: eng
  text: '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:
    (i) S contains at most one request per user, (ii) the frequency sets allotted
    to requests in S that correspond to the same base station are pairwise non-intersecting,
    and (iii) the QoS received by any user at any frequency is reasonable according
    to an interference model. In this paper 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 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. '
author:
- first_name: Reuven
  full_name: Bar-Yehuda, Reuven
  last_name: Bar-Yehuda
- first_name: Gleb
  full_name: Polevoy, Gleb
  id: '83983'
  last_name: Polevoy
- first_name: Dror
  full_name: Rawitz, Dror
  last_name: Rawitz
citation:
  ama: Bar-Yehuda R, Polevoy G, Rawitz D. Bandwidth allocation in cellular networks
    with multiple interferences. <i>Discrete Applied Mathematics </i>. 2015;194:23-36.
    doi:<a href="http://dx.doi.org/10.1016/j.dam.2015.05.013">http://dx.doi.org/10.1016/j.dam.2015.05.013</a>
  apa: Bar-Yehuda, R., Polevoy, G., &#38; Rawitz, D. (2015). Bandwidth allocation
    in cellular networks with multiple interferences. <i>Discrete Applied Mathematics
    </i>, <i>194</i>, 23–36. <a href="http://dx.doi.org/10.1016/j.dam.2015.05.013">http://dx.doi.org/10.1016/j.dam.2015.05.013</a>
  bibtex: '@article{Bar-Yehuda_Polevoy_Rawitz_2015, title={Bandwidth allocation in
    cellular networks with multiple interferences}, volume={194}, DOI={<a href="http://dx.doi.org/10.1016/j.dam.2015.05.013">http://dx.doi.org/10.1016/j.dam.2015.05.013</a>},
    journal={Discrete Applied Mathematics }, publisher={Elsevier}, author={Bar-Yehuda,
    Reuven and Polevoy, Gleb and Rawitz, Dror}, year={2015}, pages={23–36} }'
  chicago: 'Bar-Yehuda, Reuven, Gleb Polevoy, and Dror Rawitz. “Bandwidth Allocation
    in Cellular Networks with Multiple Interferences.” <i>Discrete Applied Mathematics
    </i> 194 (2015): 23–36. <a href="http://dx.doi.org/10.1016/j.dam.2015.05.013">http://dx.doi.org/10.1016/j.dam.2015.05.013</a>.'
  ieee: R. Bar-Yehuda, G. Polevoy, and D. Rawitz, “Bandwidth allocation in cellular
    networks with multiple interferences,” <i>Discrete Applied Mathematics </i>, vol.
    194, pp. 23–36, 2015.
  mla: Bar-Yehuda, Reuven, et al. “Bandwidth Allocation in Cellular Networks with
    Multiple Interferences.” <i>Discrete Applied Mathematics </i>, vol. 194, Elsevier,
    2015, pp. 23–36, doi:<a href="http://dx.doi.org/10.1016/j.dam.2015.05.013">http://dx.doi.org/10.1016/j.dam.2015.05.013</a>.
  short: R. Bar-Yehuda, G. Polevoy, D. Rawitz, Discrete Applied Mathematics  194 (2015)
    23–36.
date_created: 2020-08-06T15:21:15Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: http://dx.doi.org/10.1016/j.dam.2015.05.013
extern: '1'
intvolume: '       194'
keyword:
- Local ratio
language:
- iso: eng
page: 23 - 36
publication: 'Discrete Applied Mathematics '
publication_identifier:
  issn:
  - 0166-218X
publisher: Elsevier
status: public
title: Bandwidth allocation in cellular networks with multiple interferences
type: journal_article
user_id: '83983'
volume: 194
year: '2015'
...