2
$\begingroup$

I'm looking for implementations of approximation algorithms (or algorithms that would be meaningful to implement for use in practice) for the minimum-cost multicommodity flow problem as defined in e.g. Section 2.1 of

Andrew V. Goldberg, Jeffrey D. Oldham, Serge Plotkin & Cliff Stein An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow, https://rd.springer.com/chapter/10.1007/3-540-69346-7_26

They give a description of an $(1+\epsilon)$-approximation algorithm in that paper and have implemented it as well, but the implementation does not appear to be readily available.

And is there any newer research/implementation that supersedes the 1998 work? There's certainly a good deal of work on various related problems such as maximum concurrent multicommodity flow, but that's not really what I'm after.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Are you familiar with the width-independent MWU algorithm for the problem? $\endgroup$
    – AspiringMat
    Nov 4, 2022 at 1:25
  • $\begingroup$ Thanks @AspiringMat. I know that MWU has featured in work from the past few decades that uses electrical flows to come up with efficient methods for solving maximum flow/minimum-cost flow, and that Mądry has papers that use it to come up with approximation algorithms for some of the variations on multicommodity flow, but I don't believe I've seen an application to minimum-cost multicommodity flow, no. But maybe some of the existing work can be transferred to this one as well? $\endgroup$
    – fuglede
    Nov 4, 2022 at 7:35
  • 1
    $\begingroup$ Check the bible on MWU: cs.princeton.edu/~arora/pubs/MWsurvey.pdf . It contains a section describing the algorithm for applying MWU to the maximum-cost multi-commodity flow problem. I worked on this problem a few years ago, and as far as I remember, the width independent one is the fastest one out there. I could be wrong, my memory is hazy. I remember implementing it was very simple and it converged fairly quickly. You can adapt it for the minimum-cost variant as well. $\endgroup$
    – AspiringMat
    Nov 4, 2022 at 7:41
  • 1
    $\begingroup$ Yes, but adapting it to the minimum-cost variant should be doable (At the end of the day, MWU can be used to solve any covering/packing LP). For example, in the original paper by Garg et al, they describe the same algorithm for minimum-cost multicommodity flow. "N. Garg and J. K ̈onemann. Faster and simpler algorithms formulticommodity flow and other fractional packing problems. InProceedings of the 39th Annual Symposium on Foundations ofComputer Science(FOCS-98)" $\endgroup$
    – AspiringMat
    Nov 4, 2022 at 8:14
  • 1
    $\begingroup$ I had an implementation 5 years ago for a course project in my undergrad, but unfortunately don't have it handy now. I'll try to look up my implementation on the weekend and report here if I find it but no promises. $\endgroup$
    – AspiringMat
    Nov 4, 2022 at 8:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.