From dr.martinberger at protonmail.com Sat Mar 19 21:09:59 2022 From: dr.martinberger at protonmail.com (Martin) Date: Sat, 19 Mar 2022 21:09:59 +0000 Subject: [Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible) In-Reply-To: References: Message-ID: 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: