Hacker News new | past | comments | ask | show | jobs | submit login

This could be quite useful for Ripple, which is basically solving a max-flow min-cost problem over a credit lines graph.



Ripple is actually a generalized network flow problem, in which the flow through an edge can be multiplied by an exchange rate when converting between currencies. As a result, regular network flow algorithms don't apply. There's also another issue with using a minimum cost criterion, since the costs are in different currencies and it's not clear how to put them on the same footing.


If you make cost the log of the conversion rate plus the log of the %age fee, and treat each node as a distinct node for each currency, you do get max flow min cost.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: