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)

Summary:

The discussion on zerobasefee suggests that HTLCs are always free to an attacker. However, the argument doesn't hold up as Zmn's approach for overweighing base fee can be used to let the market decide on the relative importance of optimized routing vs base fees. Martin's approximation research on the minimum convex cost flow formulation for multi-part payments on the lightning network is paywalled and not available at sci-hub. An alternative paper by Dorit Hochbaum from 1993 proves proximity results for integer and continuous optimal solutions of the minimum convex cost flow. The paper 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 also gives near-optimal solutions on the integer domain.

Updated on: 2023-06-03T07:52:16.980125+00:00