rich1.0npub1gudxspr8gkafq0mvzrwpj5qyuhtr3euwqf08rlkdr63zhe39l30qzplrqghttps://nostr.ae/npub1gudxspr8gkafq0mvzrwpj5qyuhtr3euwqf08rlkdr63zhe39l30qzplrqgnjumphttps://nostr.ae📅 Original date posted:2022-03-19 📝 Original message: Dear Carsten, Rene and fellow lightning developers, Regarding the approximation quality of the minimum convex cost flow formulation for multi-part payments on the lightning network [1] and Carsten's discussion points on Twitter [2] and on the mailing list: > 8) Quality of Approximation > > There are some problems in computer science that are hard/impossible to > approximate, in the sense that any kind of deviation from the optimum > could cause the computed results to be extremely bad. Do you have some > idea (or proof) that your kind of approximation isn't causing a major > issue? I guess a piece-wise linearization with an infinite number of > pieces corresponds to the optimal result. Given a finite number of > pieces, how large is the difference to the optimum? I did some literature research and came across an insightful paper [3] by Dorit Hochbaum from 1993, that proves proximity results for integer and continuous optimal solutions of the minimum convex cost flow as well as proximity results of the optimal solutions for a piecewise linear approximation and the original problem. Admittedly theoretical results, however, it further underpins that a piecewise linear approximation is a reasonable approach to find optimal flows and even shows that searching for optimal solutions on the continuous domain (e.g. with descent methods from convex optimization) also gives near-optimal solutions on the integer domain. Cheers, Martin [1] https://arxiv.org/abs/2107.05322 [2] https://twitter.com/renepickhardt/status/1502293438498234371 [3] https://www.worldscientific.com/doi/abs/10.1142/9789812798190_0005 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220319/f278c153/attachment.html>