Dear Lightning Developer, Rene & Carsten, The min-cost flow formulation for MPP of Rene and Stefan [1] intrigued me and brought me to think about how this optimization problem can be solved efficiently in order to contribute to practically relevant reliable payments on the Lightning network. Applying linear approximation to the convex non-linear cost function C(f) brings runtime improvements [2], however an approximation can deteriorate the solution quality.
This brought me to think about the approximation quality/error of a piecewise linear approximation for the cost function C(f) and how that translate to the original success probability of a flow P(f). After some back and forth with Rene over the last couple of days, I summarized some preliminary insights in the following: [3] https://raw.githubusercontent.com/drmartinberger/mpp-approx-pf/main/approxPf.pdf The main (admittedly, mostly theoretical) outcome is, that a piecewise linear approximation of C(f) with given approximation error, also gives an approximation of the function P(f) with lower/upper bound. However, [3] further underpins the "goodness" of the approach [1] and might address some of Carsten's concerns [4] and of the previous post of Carsten (especially 8) ). Feedback of any kind is warmly welcome and feel free to reach out in case of questions. Thank you! Cheers, Martin [1] https://arxiv.org/abs/2107.05322 [2] https://github.com/renepickhardt/mpp-splitter/blob/master/Minimal%20Linearized%20min%20cost%20flow%20example%20for%20MPP.ipynb [3] https://raw.githubusercontent.com/drmartinberger/mpp-approx-pf/main/approxPf.pdf [4] https://twitter.com/c_otto83/status/1502329970349248521 _______________________________________________ Lightning-dev mailing list [email protected] https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
