In fact, the paper "A Combinatorial Algorithm for the Multi-commodity Flow Problem" gives two combinatorial algorithms; The first is called Cycle-canceling Algorithm, which may run exponentially long; But the second algorithm (chapter 4.3) is not an exponential time algorithm. In Chapter 4 of the paper, the author gives a nonlinear description of multi-commodity flow problem and shows that it can be solved by the Frank-Wolfe Algorithm. And the convergence of the Frank–Wolfe algorithm is sublinear. I have seriously read the paper and think the conclusion is valid. 78.155.199.200 (talk) 13:33, 29 June 2019 (UTC)
Hi (not sure how this works, feel free to email me (find my email at my website).
A) I'm not convinced that the first algorithm converges (even in exponentially many steps). In particular, I think that an augmenting cycle might not exist even if the incumbent solution is not optimal. As one specific point which confuses me, see proof of Theorem 4, "Obviously there are even alternating points on a cycle" -- this does not seem to be true and perhaps the authors means something else.
B) Even the second algorithm does not make any formal claim about the number of iterations, and it's not clear to me how strongly it relies on the first part, which I believe to contain some bugs. Having "some convergence criterion is met" in the algorithm also does not strike confidence.
I find this problem very interesting and I'm not saying the paper at hand does not contain some potential. But the previous mention on the multicommodity flow page gave it too much weight IMHO. I'll be happy to discuss more over email - please contact me. Martin Koutecký (talk) 14:25, 29 June 2019 (UTC)
Regarding the Frank-Wolfe algorithm: even if everything was correct and its convergence was sublinear, this is not fast enough and only warrants an FPTAS (an algorithm which computes an ε-approximate solution in time poly(1/ε, n)), not a polynomial algorithm. To obtain an exact algorithm one would have to prove that (1/poly(n))-accuracy is sufficient, which the paper does not do.Martin Koutecký (talk) 15:15, 29 June 2019 (UTC)