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
_______________________________________________
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
