Network flow problems are very well studied in the literature (e.g., see the Network Flows book), and the first DIMACS challenge was dedicated to these problems.

Very efficient implementation of state-of-the-art algorithms are available, for instance, in the LEMON graph library.

However, I am unable find any reference dealing for the special case of “metric network flow problems”, that is, for problems where, given the network $G=(N,A)$, the costs coefficients $c_{ij}$ associated to any arc $(i,j) \in A$ define a distance function:

  1. $c_{ij} \geq 0$ (non negativity)
  2. $c_{ij} = 0 \iff i=j$
  3. $c_{ij} = c_{ji}$ (symmetry)
  4. $c_{ik} \leq c_{ij} + c_{jk}$ (triangle inequality)

Do you know any work related to this case? If yes, does exist standard benchmarks for this case available online?

In particular, I am interested to the metric transportation problem and the metric minimum cost flow problem. Thanks.

  • 1
    $\begingroup$ Are these helpful? 1, 2, 3. I can't find exactly what you're looking for though. $\endgroup$ – TheSimpliFire Jul 10 '19 at 7:08
  • $\begingroup$ Reference 3 is very related to my question, and, indeed, my question is motivated by Discrete Optimal Transport applications. I will look it careful, thanks a lot! $\endgroup$ – Stefano Gualandi Jul 10 '19 at 7:19
  • $\begingroup$ @TheSimpliFire: I think you can write an answer using reference 3, and the references therein contained. $\endgroup$ – Stefano Gualandi Jul 10 '19 at 7:34

The following references do not completely answer the idea of a metric (that satisfies the triangle inequality) as said by the OP they are still useful.

Under network flow, Emami (2018) describes several algorithms that can be used to tackle the geometric transportation problem.

  • The exact geometric algorithm

The main contribution of this paper is that, when the ground distance is the $l_1$, $l_2$, or $l_\infty$ norm, the algorithm runs in $\mathcal O(n^{2.5}\log n \log N)$.

The author describes the results by Atkinson and Vaidya (1995) through the weighted Voronoi diagram (WVD). Where this fits into the question is that in such a diagram, the distance between cells can satisfy the standard Euclidean metric.

  • The approximate geometric algorithm

In fact, there are two such algorithms proposed by Agarwal et al. (2017).

The first is a randomized $\epsilon$-approximation algorithm that finds the optimal transportation in $\mathcal O(n^{1+\epsilon})$ expected time whose expected cost is $\mathcal O(\log(1/\epsilon))\mu(\tau^*)$ if the spread of $A \cup B$ is bounded by some polynomial. This algorithm uses randomly-shifted grids to recursively decompose the problem into a set of easier subproblems that are solved by Orlin’s algorithm.

The second algorithm described is a $(1 + \epsilon)$ approximation algorithm that finds a transportation plan with cost $(1 + \epsilon)\mu(\tau^*)$ in time $\mathcal O(n^{1.5}\epsilon^{-d}\operatorname{polylog}(U)\operatorname{polylog}(n))$. The algorithm constructs an efficient representation of the pairwise distances between the point sets, and then makes use of Lee and Sidford’s min-cost flow algorithm on the resulting flow graph.

NB There is a post here on OR.SE that explains the difference between exact and approximate.

Finally, there is an older paper by Lim et al. (2006) that studies a transportation problem with minimum quality commitment (MQC).

The transportation problem with MQC can be classified into two classes: the metric version and the non-metric version. The metric version makes the restriction that the transportation costs satisfy the triangular inequality. In other words, in the metric version, $c_{i,j}$ depends on the distance between the location of carrier $i$ and the location of customer $j$ which forms a metric. The metric version is practical in some real applications. [...] This paper focuses on the non-metric version of the transportation problem with MQC; in terms of the computational complexities [...] The other [heuristic] is a greedy heuristic, whose solution quality depends on the scale of the minimum quantity when the transportation cost forms a distance metric.

It is also proven that the transportation problem with MQC and metric transportation costs in $\sf{NP}$-hard.


[1] Emami, P. (2018). Algorithms for the Geometric Transportation Problem. Available from: https://pemami4911.github.io/cs-dojo/algorithms-geometric-transportation.pdf.

[2] Atkinson, D. S., Vaidya, P. M. (1995) Using geometry to solve the transportation problem in the plane. Algorithmica. 13(5):442–461.

[3] Agarwal, P. K., Fox, K., Panigrahi, D., Varadarajan, K. R., Xiao, A. (2017). Faster algorithms for the geometric transportation problem. Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017).

[4] Lim, A., Wang, F., Xu, Z. (2006). A Transportation Problem with Minimum Quantity Commitment. Transportation Science. 40(1):117-129.


Your Answer

