[{"place":"Cham","citation":{"short":"G. Polevoy, S. Trajanovski, P. Grosso, C. de Laat, in: D. Kim, R.N. Uma, A. Zelikovsky (Eds.), Combinatorial Optimization and Applications, Springer International Publishing, Cham, 2018, pp. 217–232.","chicago":"Polevoy, Gleb, Stojan Trajanovski, Paola Grosso, and Cees de Laat. “Removing Undesirable Flows by Edge Deletion.” In <i>Combinatorial Optimization and Applications</i>, edited by Donghyun Kim, R. N. Uma, and Alexander Zelikovsky, 217–32. Cham: Springer International Publishing, 2018.","ieee":"G. Polevoy, S. Trajanovski, P. Grosso, and C. de Laat, “Removing Undesirable Flows by Edge Deletion,” in <i>Combinatorial Optimization and Applications</i>, 2018, pp. 217–232.","apa":"Polevoy, G., Trajanovski, S., Grosso, P., &#38; de Laat, C. (2018). Removing Undesirable Flows by Edge Deletion. In D. Kim, R. N. Uma, &#38; A. Zelikovsky (Eds.), <i>Combinatorial Optimization and Applications</i> (pp. 217–232). Cham: Springer International Publishing.","bibtex":"@inproceedings{Polevoy_Trajanovski_Grosso_de Laat_2018, place={Cham}, title={Removing Undesirable Flows by Edge Deletion}, booktitle={Combinatorial Optimization and Applications}, publisher={Springer International Publishing}, author={Polevoy, Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees}, editor={Kim, Donghyun and Uma, R. N. and Zelikovsky, AlexanderEditors}, year={2018}, pages={217–232} }","ama":"Polevoy G, Trajanovski S, Grosso P, de Laat C. Removing Undesirable Flows by Edge Deletion. In: Kim D, Uma RN, Zelikovsky A, eds. <i>Combinatorial Optimization and Applications</i>. Cham: Springer International Publishing; 2018:217-232.","mla":"Polevoy, Gleb, et al. “Removing Undesirable Flows by Edge Deletion.” <i>Combinatorial Optimization and Applications</i>, edited by Donghyun Kim et al., Springer International Publishing, 2018, pp. 217–32."},"_id":"17651","publisher":"Springer International Publishing","page":"217-232","editor":[{"full_name":"Kim, Donghyun","last_name":"Kim","first_name":"Donghyun"},{"first_name":"R. N.","last_name":"Uma","full_name":"Uma, R. N."},{"full_name":"Zelikovsky, Alexander","first_name":"Alexander","last_name":"Zelikovsky"}],"user_id":"83983","status":"public","date_created":"2020-08-06T15:19:36Z","department":[{"_id":"63"},{"_id":"541"}],"type":"conference","keyword":["flow","Red-Blue Set Cover","Positive-Negative Partial Set Cover","approximation","tree","MAX SNP-hard","root","leaf","dynamic programming","FPT"],"publication":"Combinatorial Optimization and Applications","abstract":[{"text":"Consider mitigating the effects of denial of service or of malicious traffic in networks by deleting edges. Edge deletion reduces the DoS or the number of the malicious flows, but it also inadvertently removes some of the desired flows. To model this important problem, we formulate two problems: (1) remove all the undesirable flows while minimizing the damage to the desirable ones and (2) balance removing the undesirable flows and not removing too many of the desirable flows. We prove these problems are equivalent to important theoretical problems, thereby being important not only practically but also theoretically, and very hard to approximate in a general network. We employ reductions to nonetheless approximate the problem and also provide a greedy approximation. When the network is a tree, the problems are still MAX SNP-hard, but we provide a greedy-based 2l-approximation algorithm, where l is the longest desirable flow. We also provide an algorithm, approximating the first and the second problem within {\\$}{\\$}2 {\\backslash}sqrt{\\{} 2{\\backslash}left| E {\\backslash}right| {\\}}{\\$}{\\$}and {\\$}{\\$}2 {\\backslash}sqrt{\\{}2 ({\\backslash}left| E {\\backslash}right| + {\\backslash}left| {\\backslash}text {\\{}undesirable flows{\\}} {\\backslash}right| ){\\}}{\\$}{\\$}, respectively, where E is the set of the edges of the network. We also provide a fixed-parameter tractable (FPT) algorithm. Finally, if the tree has a root such that every flow in the tree flows on the path from the root to a leaf, we solve the problem exactly using dynamic programming.","lang":"eng"}],"extern":"1","language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-3-030-04651-4"]},"author":[{"full_name":"Polevoy, Gleb","first_name":"Gleb","last_name":"Polevoy","id":"83983"},{"first_name":"Stojan","last_name":"Trajanovski","full_name":"Trajanovski, Stojan"},{"full_name":"Grosso, Paola","first_name":"Paola","last_name":"Grosso"},{"full_name":"de Laat, Cees","last_name":"de Laat","first_name":"Cees"}],"year":"2018","title":"Removing Undesirable Flows by Edge Deletion","date_updated":"2022-01-06T06:53:16Z"},{"citation":{"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>","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.","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} }","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>.","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."},"place":"Cham","status":"public","page":"3-17","_id":"17652","publisher":"Springer International Publishing","user_id":"83983","publication":"Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I","extern":"1","date_created":"2020-08-06T15:19:48Z","keyword":["flow","filter","MMSA","set cover","approximation","local ratio algorithm"],"type":"conference","department":[{"_id":"63"},{"_id":"541"}],"year":"2017","title":"Filtering Undesirable Flows in Networks","publication_identifier":{"isbn":["978-3-319-71150-8"]},"author":[{"full_name":"Polevoy, Gleb","first_name":"Gleb","last_name":"Polevoy","id":"83983"},{"full_name":"Trajanovski, Stojan","first_name":"Stojan","last_name":"Trajanovski"},{"full_name":"Grosso, Paola","first_name":"Paola","last_name":"Grosso"},{"full_name":"de Laat, Cees","last_name":"de Laat","first_name":"Cees"}],"date_updated":"2022-01-06T06:53:16Z","series_title":"Lecture Notes in Computer Science","language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-71150-8_1"},{"article_type":"original","intvolume":"        14","publication_status":"published","date_updated":"2023-02-28T11:02:47Z","author":[{"full_name":"Gharibian, Sevag","last_name":"Gharibian","first_name":"Sevag","orcid":"0000-0002-9992-3379","id":"71541"},{"last_name":"Kempe","first_name":"Julia","full_name":"Kempe, Julia"}],"year":"2014","title":"Hardness of approximation for quantum problems","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1209.1055"}],"extern":"1","abstract":[{"text":"The polynomial hierarchy plays a central role in classical complexity theory. Here, we define\r\na quantum generalization of the polynomial hierarchy, and initiate its study. We show that\r\nnot only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Using the same techniques, we\r\nalso obtain hardness of approximation for the class QCMA. Our approach is based on the\r\nuse of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy [Umans, FOCS 1999].\r\nThe problems for which we prove hardness of approximation for include, among others, a\r\nquantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian\r\nproblem with hybrid classical-quantum ground states.","lang":"eng"}],"issue":"5-6","publication":"Quantum Information & Computation","department":[{"_id":"623"},{"_id":"7"}],"type":"journal_article","keyword":["Hardness of approximation","polynomial time hierarchy","succinct set cover","quantum complexity"],"date_created":"2019-03-01T11:56:55Z","status":"public","volume":14,"user_id":"71541","_id":"8171","page":"517-540","citation":{"apa":"Gharibian, S., &#38; Kempe, J. (2014). Hardness of approximation for quantum problems. <i>Quantum Information &#38; Computation</i>, <i>14</i>(5–6), 517–540.","ieee":"S. Gharibian and J. Kempe, “Hardness of approximation for quantum problems,” <i>Quantum Information &#38; Computation</i>, vol. 14, no. 5–6, pp. 517–540, 2014.","chicago":"Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” <i>Quantum Information &#38; Computation</i> 14, no. 5–6 (2014): 517–40.","short":"S. Gharibian, J. Kempe, Quantum Information &#38; Computation 14 (2014) 517–540.","mla":"Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.” <i>Quantum Information &#38; Computation</i>, vol. 14, no. 5–6, 2014, pp. 517–40.","ama":"Gharibian S, Kempe J. Hardness of approximation for quantum problems. <i>Quantum Information &#38; Computation</i>. 2014;14(5-6):517-540.","bibtex":"@article{Gharibian_Kempe_2014, title={Hardness of approximation for quantum problems}, volume={14}, number={5–6}, journal={Quantum Information &#38; Computation}, author={Gharibian, Sevag and Kempe, Julia}, year={2014}, pages={517–540} }"},"oa":"1","external_id":{"arxiv":["1209.1055"]}}]