Maximum Flow Reduction with Cross Dependencies

Question

I have n jobs which are done using an old system. If I change them to a new system, I get bi benefit for that job. Some job pairs (i,j) have dependencies. Changing a job but not its dependent pair cost xij. Job 1 cannot run under the new system. What is the ideal set of jobs to change to the new system (excluding job 1 of course) to maximize benefit.

This is an algorithm problem rephrased in my own words. It is supposed to be reduced to some form of max flow or circulation. I am having extreme trouble coming up with an approach due the fact that the costs are dependent on other jobs being changed to the new system (I cannot seem to associate static values to a max-flow graph setup and have a working solution). I have thought about this for some time and am still struggling to find a decent approach. Any suggestions about how to think about attacking this problem would be much appreciated!

Answer 1

Let's assign b₁ = −∞.

After that simple reduction, what you describe is exactly the maximum blocking-cut problem, for example defined in "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.

They continue to draw a connection between the maximum blocking-cut problem and the min-cut problem. For that, the define V' = V ∪ { s,t } and A' = A ∪ { (s,i) | w_i > 0 } ∪ { (j,t) | w_j < 0 }. Then they define the arc capacities c_si = w_i if w_i > 0 and c_jt = −w_j if w_j < 0. We then have

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.

The latter problem can be solved easily using a maximum-flow algorithm, by utilizing the max-flow min-cut theorem. In fact you can use job 1 as the source since it is guaranteed to be part of the source set (the jobs running on the old machine).