{"type":"rich","version":"1.0","author_name":"npub1gudxspr8gkafq0mvzrwpj5qyuhtr3euwqf08rlkdr63zhe39l30qzplrqg","author_url":"https://nostr.ae/npub1gudxspr8gkafq0mvzrwpj5qyuhtr3euwqf08rlkdr63zhe39l30qzplrqg","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2022-03-14\n📝 Original message:\nDear Lightning Developer, Rene \u0026 Carsten,\n\nThe 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.\n\nThis 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:\n\n[3] https://raw.githubusercontent.com/drmartinberger/mpp-approx-pf/main/approxPf.pdf\n\nThe 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.\nHowever, [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) ).\n\nFeedback of any kind is warmly welcome and feel free to reach out in case of questions.\n\nThank you!\n\nCheers,\nMartin\n\n[1] https://arxiv.org/abs/2107.05322\n[2] https://github.com/renepickhardt/mpp-splitter/blob/master/Minimal%20Linearized%20min%20cost%20flow%20example%20for%20MPP.ipynb\n[3] https://raw.githubusercontent.com/drmartinberger/mpp-approx-pf/main/approxPf.pdf\n[4] https://twitter.com/c_otto83/status/1502329970349248521"}