Martin [ARCHIVE] on Nostr: 📅 Original date posted:2022-03-19 📝 Original message: Dear Carsten, Rene and ...
📅 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>;
📝 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>;