English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In the Network Flow Interdiction problem an adversary attacks a network inorder to minimize the maximum s-t-flow. Very little is known about theapproximatibility of this problem despite decades of interest in it. We presentthe first approximation hardness, showing that Network Flow Interdiction andseveral of its variants cannot be much easier to approximate than Densestk-Subgraph. In particular, any $n^{o(1)}$-approximation algorithm for NetworkFlow Interdiction would imply an $n^{o(1)}$-approximation algorithm for Densestk-Subgraph. We complement this hardness results with the first approximationalgorithm for Network Flow Interdiction, which has approximation ratio 2(n-1).We also show that Network Flow Interdiction is essentially the same as theBudgeted Minimum s-t-Cut problem, and transferring our results gives the firstapproximation hardness and algorithm for that problem, as well.

Hardness and Approximation for Network Flow Interdiction