From richter at cs.rwth-aachen.de Sun Mar 20 09:07:01 2022 From: richter at cs.rwth-aachen.de (Stefan Richter) Date: Sun, 20 Mar 2022 10:07:01 +0100 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: Good morning everyone, with regards to zerobasefee, I think that the argument that HTLCs are costly doesn't quite hold up because they are always free to an attacker as it stands. However, I fully agree with Zmn's opinion that it's not necessary to bang our head against any opposition to this because we can simply follow his excellent method for overweighing base fee. I believe this is a very natural approach to let the market decide on the relative importance of optimized routing vs base fees. As to Martin's approximation research, I have asked myself similar questions. Unfortunately, the paper you cite is paywalled and not available at sci-hub, so I haven't read it. FWIW, I believe I have a simple proof that minimum cost flow preserves approximation FACTORS: Let O be the original problem and A the approximated problem such that every flow in O can be mapped 1:1 to a flow in A and vice versa. Let every edge e in O be represented by a set of edges in A whose total cost is within a factor (1+epsilon) for every possible flow (could be over- or underestimating). Note that this means that every flow in O has cost within a factor (1+epsilon) for the corresponding flow in A and vice versa. Now let f_a be the min cost flow in A and f_o the min cost flow in O. Assume that c(f_o)(1+epsilon): > > 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 at lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev