1
$\begingroup$

Is there a standard name or a reference for the network flow problem that looks very similar to the minimum cost maximum flow problem, only the flow cost that I wish to minimize isn't sum of edge.flow * edge.weight over edges, but rather sum of [edge.flow > 0] * edge.weight over edges, where [edge.flow > 0] equals one if the flow is greater than zero, and zero otherwise? Is it intractable, as I suspect?

I'll tell you about the original problem that I believe reduces to this problem. A bunch of friends have a dinner, and agree to split the bill evenly. But not everyone has enough money to cover their share at that moment, so some pay more than their share, some less, with the intent to settle later. Later on, they want to settle with a minimum number of transactions, where one transaction is money changing hands between a pair of friends.

This clearly maps to a bipartite network with edges of unlimited capacity from all the ones who underpaid going to all of those who overpaid, and edges of capacity equal to the amount underpaid going from source to the underpaid nodes, and edges of capacity equal to the amount overpaid going from overpaid nodes to the sink. To minimize the number of transactions we need to minimize the number of nonzero flow edges between the under- and overpaid.

Improve this question
$\endgroup$
6
  • $\begingroup$ It looks like the descriptions are contradicting to each other. Can you add a simple non-trivial example in the question? $\endgroup$ – John L. Jul 4 '19 at 3:46
  • $\begingroup$ @Apass.Jack sorry, can you be more specific as to what exactly contradicts what? $\endgroup$ – Mio Jul 4 '19 at 14:54
  • $\begingroup$ The "minimum number of transactions" is not "sum of [edge.flow > 0] * edge.weight over edges". $\endgroup$ – John L. Jul 4 '19 at 15:11
  • $\begingroup$ @Apass.Jack you're right, one is more general than the other. I believe when we set all edge weights to be equal we get the dinner problem that I described. $\endgroup$ – Mio Jul 4 '19 at 15:18
  • $\begingroup$ Anyway, you may want to check this question and answer. $\endgroup$ – John L. Jul 4 '19 at 15:24
2
$\begingroup$

This is sometimes called the minimum edge-cost flow problem or fixed-cost flow problem. As you suspected, it is indeed NP-hard, even when the network is bipartite. It is listed as problem ND32 in the list of NP-hard problems by Garey and Johnson:

M.R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.

An approximation algorithm is discussed here:

S.O. Krumke, H. Noltemeier, S. Schwarz, H.-C. Wirth, R. Ravi. Flow Improvement and Network Flows with Fixed Costs. In Operations Research Proceedings 1998: Selected Papers of the International Conference on Operations Research Zurich, p. 158--167, Springer, Berlin, 1998.

The idea is to solve a standard linear-cost flow problem in which edge capacities are unchanged, but the cost of one unit of flow along edge $e$ is defined to be the edge weight divided by the edge capacity. This will give a solution that may weigh up to $F$ times the weight of the optimal solution, where $F$ is the flow value; but it will not weigh more than that.

If the approximate solution is not good enough, you might want to resort to an ILP solver.

Improve this answer
$\endgroup$

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.