论文标题
在两粒子上最大流网络拦截问题
On the Bicriterion Maximum Flow Network Interdiction Problem
论文作者
论文摘要
本文重点介绍了最大流网络插入问题的生物主体扩展，其中网络中的每个弧都与两个容量值相关联。分别相对于第一和第二容量函数，将相互独立地计算从源到水槽的两个最大流量，而审判员的目的是通过禁止弧形来最大程度地减少两个最大流量的值。我们表明，这个问题是棘手的，并且询问可行的拦截策略是否有效的决策问题是NP的完整策略。在两末端串联图和积极的整数插入成本的情况下，我们提出了一种伪多元时间算法。我们通过适当地分区目标空间将该算法扩展到单位插入成本的情况下的完全多项式时间近似方案。
This article focuses on a biobjective extension of the maximum flow network interdiction problem, where each arc in the network is associated with two capacity values. Two maximum flows from a source to a sink are to be computed independently of each other with respect to the first and second capacity function, respectively, while an interdictor aims to minimize the value of both maximum flows by interdicting arcs. We show that this problem is intractable and that the decision problem, which asks whether or not a feasible interdiction strategy is efficient, is NP-complete. We propose a pseudopolynomial time algorithm in the case of two-terminal series-parallel graphs and positive integer-valued interdiction costs. We extend this algorithm to a fully polynomial-time approximation scheme for the case of unit interdiction costs by appropriately partitioning the objective space.
