rich1.0npub19fnl48y9j4fk9w0a284mqvszq6fuppelqp2tcxf0s37l95avdtussf4wf0https://nostr.ae/npub19fnl48y9j4fk9w0a284mqvszq6fuppelqp2tcxf0s37l95avdtussf4wf0njumphttps://nostr.ae📅 Original date posted:2022-03-20 📝 Original message: 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)<c(f_a). Then f_o corresponds to a flow in A that is cheaper than f_a, but that's impossible because f_a is the min cost flow. QED. Problems might arise anyway because we represent probabilities only logarithmically in the cost, so that a factor of (1+epsilon) corresponds to an exponent (1+epsilon) for the probabilities. But René seems optimistic that the resulting flows look good enough in practice. I am still optimistic that exact solvers with something like the cost scaling approach might also be feasible (as long as they produce integer flows), but I am happy that this simple approximation approach seems good enough. This should save us a lot of work because there are many linear min cost solvers available that represent years of cumulative work in optimization research. Cheers Stefan Am Sa., 19. März 2022 um 22:09 Uhr schrieb Martin via Lightning-dev <lightning-dev at lists.linuxfoundation.org>: > > 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