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:
- since the weights are real, setting alpha is not that easy (but I guess that a large enough alpha will work well in practice)
- this method is terribly slow
- 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?