@inproceedings{17651,
  abstract     = {{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       = {{Polevoy, Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees}},
  booktitle    = {{Combinatorial Optimization and Applications}},
  editor       = {{Kim, Donghyun and Uma, R. N. and Zelikovsky, Alexander}},
  isbn         = {{978-3-030-04651-4}},
  keywords     = {{flow, Red-Blue Set Cover, Positive-Negative Partial Set Cover, approximation, tree, MAX SNP-hard, root, leaf, dynamic programming, FPT}},
  pages        = {{217--232}},
  publisher    = {{Springer International Publishing}},
  title        = {{{Removing Undesirable Flows by Edge Deletion}}},
  year         = {{2018}},
}

@inproceedings{17652,
  author       = {{Polevoy, Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees}},
  booktitle    = {{Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I}},
  isbn         = {{978-3-319-71150-8}},
  keywords     = {{flow, filter, MMSA, set cover, approximation, local ratio algorithm}},
  pages        = {{3--17}},
  publisher    = {{Springer International Publishing}},
  title        = {{{Filtering Undesirable Flows in Networks}}},
  doi          = {{10.1007/978-3-319-71150-8_1}},
  year         = {{2017}},
}

@article{8171,
  abstract     = {{The polynomial hierarchy plays a central role in classical complexity theory. Here, we define
a quantum generalization of the polynomial hierarchy, and initiate its study. We show that
not 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
also obtain hardness of approximation for the class QCMA. Our approach is based on the
use 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].
The problems for which we prove hardness of approximation for include, among others, a
quantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian
problem with hybrid classical-quantum ground states.}},
  author       = {{Gharibian, Sevag and Kempe, Julia}},
  journal      = {{Quantum Information & Computation}},
  keywords     = {{Hardness of approximation, polynomial time hierarchy, succinct set cover, quantum complexity}},
  number       = {{5-6}},
  pages        = {{517--540}},
  title        = {{{Hardness of approximation for quantum problems}}},
  volume       = {{14}},
  year         = {{2014}},
}