[{"publication_identifier":{"isbn":["978-3-319-71150-8"]},"year":"2017","place":"Cham","page":"3-17","citation":{"ieee":"G. Polevoy, S. Trajanovski, P. Grosso, and C. de Laat, “Filtering Undesirable Flows in Networks,” in <i>Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I</i>, 2017, pp. 3–17.","chicago":"Polevoy, Gleb, Stojan Trajanovski, Paola Grosso, and Cees de Laat. “Filtering Undesirable Flows in Networks.” In <i>Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I</i>, 3–17. Lecture Notes in Computer Science. Cham: Springer International Publishing, 2017. <a href=\"https://doi.org/10.1007/978-3-319-71150-8_1\">https://doi.org/10.1007/978-3-319-71150-8_1</a>.","ama":"Polevoy G, Trajanovski S, Grosso P, de Laat C. Filtering Undesirable Flows in Networks. In: <i>Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I</i>. Lecture Notes in Computer Science. Cham: Springer International Publishing; 2017:3-17. doi:<a href=\"https://doi.org/10.1007/978-3-319-71150-8_1\">10.1007/978-3-319-71150-8_1</a>","apa":"Polevoy, G., Trajanovski, S., Grosso, P., &#38; de Laat, C. (2017). Filtering Undesirable Flows in Networks. In <i>Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I</i> (pp. 3–17). Cham: Springer International Publishing. <a href=\"https://doi.org/10.1007/978-3-319-71150-8_1\">https://doi.org/10.1007/978-3-319-71150-8_1</a>","mla":"Polevoy, Gleb, et al. “Filtering Undesirable Flows in Networks.” <i>Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I</i>, Springer International Publishing, 2017, pp. 3–17, doi:<a href=\"https://doi.org/10.1007/978-3-319-71150-8_1\">10.1007/978-3-319-71150-8_1</a>.","bibtex":"@inproceedings{Polevoy_Trajanovski_Grosso_de Laat_2017, place={Cham}, series={Lecture Notes in Computer Science}, title={Filtering Undesirable Flows in Networks}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-71150-8_1\">10.1007/978-3-319-71150-8_1</a>}, booktitle={Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I}, publisher={Springer International Publishing}, author={Polevoy, Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees}, year={2017}, pages={3–17}, collection={Lecture Notes in Computer Science} }","short":"G. Polevoy, S. Trajanovski, P. Grosso, C. de Laat, in: Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I, Springer International Publishing, Cham, 2017, pp. 3–17."},"date_updated":"2022-01-06T06:53:16Z","publisher":"Springer International Publishing","date_created":"2020-08-06T15:19:48Z","author":[{"last_name":"Polevoy","full_name":"Polevoy, Gleb","id":"83983","first_name":"Gleb"},{"full_name":"Trajanovski, Stojan","last_name":"Trajanovski","first_name":"Stojan"},{"full_name":"Grosso, Paola","last_name":"Grosso","first_name":"Paola"},{"first_name":"Cees","full_name":"de Laat, Cees","last_name":"de Laat"}],"title":"Filtering Undesirable Flows in Networks","doi":"10.1007/978-3-319-71150-8_1","publication":"Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I","type":"conference","status":"public","_id":"17652","department":[{"_id":"63"},{"_id":"541"}],"series_title":"Lecture Notes in Computer Science","user_id":"83983","keyword":["flow","filter","MMSA","set cover","approximation","local ratio algorithm"],"language":[{"iso":"eng"}],"extern":"1"},{"publication_identifier":{"issn":["0166-218X"]},"year":"2015","page":"23 - 36","intvolume":"       194","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>","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.","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} }","short":"R. Bar-Yehuda, G. Polevoy, D. Rawitz, Discrete Applied Mathematics  194 (2015) 23–36.","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>."},"publisher":"Elsevier","date_updated":"2022-01-06T06:53:16Z","volume":194,"author":[{"first_name":"Reuven","last_name":"Bar-Yehuda","full_name":"Bar-Yehuda, Reuven"},{"first_name":"Gleb","id":"83983","full_name":"Polevoy, Gleb","last_name":"Polevoy"},{"last_name":"Rawitz","full_name":"Rawitz, Dror","first_name":"Dror"}],"date_created":"2020-08-06T15:21:15Z","title":"Bandwidth allocation in cellular networks with multiple interferences","doi":"http://dx.doi.org/10.1016/j.dam.2015.05.013","publication":"Discrete Applied Mathematics ","type":"journal_article","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. "}],"status":"public","_id":"17658","department":[{"_id":"63"},{"_id":"541"}],"user_id":"83983","keyword":["Local ratio"],"extern":"1","language":[{"iso":"eng"}]}]