# Best way to improve max-flow on a DAG

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?

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}