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, privacy policy and cookie policy