---
_id: '17651'
abstract:
- lang: eng
  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.'
author:
- first_name: Gleb
  full_name: Polevoy, Gleb
  id: '83983'
  last_name: Polevoy
- first_name: Stojan
  full_name: Trajanovski, Stojan
  last_name: Trajanovski
- first_name: Paola
  full_name: Grosso, Paola
  last_name: Grosso
- first_name: Cees
  full_name: de Laat, Cees
  last_name: de Laat
citation:
  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.'
  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}
    }'
  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.
  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.
  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.'
date_created: 2020-08-06T15:19:36Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
editor:
- first_name: Donghyun
  full_name: Kim, Donghyun
  last_name: Kim
- first_name: R. N.
  full_name: Uma, R. N.
  last_name: Uma
- first_name: Alexander
  full_name: Zelikovsky, Alexander
  last_name: Zelikovsky
extern: '1'
keyword:
- flow
- Red-Blue Set Cover
- Positive-Negative Partial Set Cover
- approximation
- tree
- MAX SNP-hard
- root
- leaf
- dynamic programming
- FPT
language:
- iso: eng
page: 217-232
place: Cham
publication: Combinatorial Optimization and Applications
publication_identifier:
  isbn:
  - 978-3-030-04651-4
publisher: Springer International Publishing
status: public
title: Removing Undesirable Flows by Edge Deletion
type: conference
user_id: '83983'
year: '2018'
...
---
_id: '17652'
author:
- first_name: Gleb
  full_name: Polevoy, Gleb
  id: '83983'
  last_name: Polevoy
- first_name: Stojan
  full_name: Trajanovski, Stojan
  last_name: Trajanovski
- first_name: Paola
  full_name: Grosso, Paola
  last_name: Grosso
- first_name: Cees
  full_name: de Laat, Cees
  last_name: de Laat
citation:
  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>'
  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} }'
  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>.'
  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.'
  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>.'
  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_created: 2020-08-06T15:19:48Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-319-71150-8_1
extern: '1'
keyword:
- flow
- filter
- MMSA
- set cover
- approximation
- local ratio algorithm
language:
- iso: eng
page: 3-17
place: Cham
publication: 'Combinatorial Optimization and Applications: 11th International Conference,
  COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I'
publication_identifier:
  isbn:
  - 978-3-319-71150-8
publisher: Springer International Publishing
series_title: Lecture Notes in Computer Science
status: public
title: Filtering Undesirable Flows in Networks
type: conference
user_id: '83983'
year: '2017'
...
---
_id: '8171'
abstract:
- lang: eng
  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."
article_type: original
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Julia
  full_name: Kempe, Julia
  last_name: Kempe
citation:
  ama: Gharibian S, Kempe J. Hardness of approximation for quantum problems. <i>Quantum
    Information &#38; Computation</i>. 2014;14(5-6):517-540.
  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.
  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} }'
  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.'
  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.
  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.
  short: S. Gharibian, J. Kempe, Quantum Information &#38; Computation 14 (2014) 517–540.
date_created: 2019-03-01T11:56:55Z
date_updated: 2023-02-28T11:02:47Z
department:
- _id: '623'
- _id: '7'
extern: '1'
external_id:
  arxiv:
  - '1209.1055'
intvolume: '        14'
issue: 5-6
keyword:
- Hardness of approximation
- polynomial time hierarchy
- succinct set cover
- quantum complexity
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1209.1055
oa: '1'
page: 517-540
publication: Quantum Information & Computation
publication_status: published
status: public
title: Hardness of approximation for quantum problems
type: journal_article
user_id: '71541'
volume: 14
year: '2014'
...