0
$\begingroup$

I am considering a problem related to max-flow on a weighted DAG and I saw a number of posts with related questions but nothing that really helps me.

I have a weighted DAG D = (V, A, W), a source S, a target T, and a budget B of weight that I can add to the arcs to increase the flow between S and T. The goal is to maximize the flow between S and T using the budget in the best way possible. Now, a simple solution would be to compute the min-cut, pick $a$ random arc a from the set of arcs identified in this way, add weight of B/alpha to $a$, and restart the procedure alpha times.

I have a few problems with this solutions:

  1. since the weights are real, setting alpha is not that easy (but I guess that a large enough alpha will work well in practice)
  2. this method is terribly slow
  3. I don't have any kind of theoretical guarantee (which I guess can be found but I don't have it yet)

Are you aware of any previous work in this area providing principled and efficient algorithms for this problem?

$\endgroup$
0
$\begingroup$

You can solve the problem via linear programming as follows. Let $x_{i,j} \ge 0$ be the flow across arc $(i,j)$, and let $y_{i,j} \ge 0$ be the weight added to arc $(i,j)$. The problem is to maximize $\sum_{(S,j)\in A} x_{S,j}$ subject to \begin{align} \sum_{(i,j)\in A} x_{i,j} - \sum_{(j,i)\in A} x_{j,i} &= 0 &&\text{for $i\in N \setminus\{S,T\}$} \\ x_{i,j} &\le c_{i,j} + y_{i,j} &&\text{for $(i,j)\in A$} \\ \sum_{(i,j)\in A} y_{i,j} &\le B \end{align}

$\endgroup$
4
  • $\begingroup$ Good point. The formulation makes a lot of sense to me, but I wonder how fast/slow solving this is going to be. $\endgroup$
    – giz
    Dec 15 '20 at 8:08
  • $\begingroup$ LP solvers are generally fast. The network simplex algorithm might perform particularly well because of the first set of constraints. $\endgroup$
    – RobPratt
    Dec 15 '20 at 13:56
  • $\begingroup$ Thanks. I will take a look. $\endgroup$
    – giz
    Dec 16 '20 at 14:22
  • $\begingroup$ Glad to help. Please mark my answer as accepted. $\endgroup$
    – RobPratt
    Dec 16 '20 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.