algorithm - 具有交叉依赖性的最大流量减少

Question

我有 n 个工作是使用旧系统完成的。如果我将它们更改为新系统，我将获得这份工作的双倍 yield 。一些作业对 (i,j) 具有依赖性。换一份工作但不换一份工作，成本为 xij。作业 1 无法在新系统下运行。为使 yield 最大化而更改为新系统的理想工作集是什么(当然不包括工作 1)。

这是一个用我自己的话改写的算法问题。它应该减少到某种形式的最大流量或循环。由于成本取决于将其他作业更改为新系统这一事实，我在想出一种方法时遇到了极大的麻烦(我似乎无法将静态值与最大流图设置相关联并有一个可行的解决方案)。我已经考虑了一段时间，但仍在努力寻找合适的方法。非常感谢任何有关如何考虑解决此问题的建议!

Answer 1

让我们分配 b₁ = −∞。

在那个简单的归约之后，你所描述的正是最大阻塞切割问题，例如在"The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem", Hochbaum 2008中定义的:

Given a directed graph G = (V, A), node weights positive or negative w_i for all i ∈ V, and non-negative arc weights c_ij for all (i,j) ∈ A. [...] Find a subset of nodes S ⊆ V such that

is maximal.

他们继续在最大阻塞切割问题和最小切割问题之间建立联系。为此，定义 V' = V ∪ { s,t } 和 A' = A ∪ { (s,i) | w_i> 0 } ∪ { (j,t) | } w_j < 0 }。然后他们定义弧容量 c_si = w_i if w_i> 0 和 c_jt = −w_j 如果 w_j < 0。然后我们有

For S ⊆ V, {s} ∪ S is the source set of a minimum cut in G_st = (V', A') if and only if (S, V \ S) is a maximum blocking cut in the graph G.

后一个问题可以使用最大流算法轻松解决，方法是利用 max-flow min-cut theorem .事实上，您可以使用作业 1 作为源，因为它保证是源集的一部分(在旧机器上运行的作业)。