{"type":"rich","version":"1.0","author_name":"npub19fnl48y9j4fk9w0a284mqvszq6fuppelqp2tcxf0s37l95avdtussf4wf0","author_url":"https://nostr.ae/npub19fnl48y9j4fk9w0a284mqvszq6fuppelqp2tcxf0s37l95avdtussf4wf0","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2022-03-20\n📝 Original message:\nGood morning everyone,\n\nwith regards to zerobasefee, I think that the argument that HTLCs are\ncostly doesn't quite hold up because they are always free to an\nattacker as it stands. However, I fully agree with Zmn's opinion that\nit's not necessary to bang our head against any opposition to this\nbecause we can simply follow his excellent method for overweighing\nbase fee. I believe this is a very natural approach to let the market\ndecide on the relative importance of optimized routing vs base fees.\n\nAs to Martin's approximation research, I have asked myself similar\nquestions. Unfortunately, the paper you cite is paywalled and not\navailable at sci-hub, so I haven't read it. FWIW, I believe I have a\nsimple proof that minimum cost flow preserves approximation FACTORS:\n\nLet O be the original problem and A the approximated problem such that\nevery flow in O can be mapped 1:1 to a flow in A and vice versa. Let\nevery edge e in O be represented by a set of edges in A whose total\ncost is within a factor (1+epsilon) for every possible flow (could be\nover- or underestimating). Note that this means that every flow in O\nhas cost within a factor (1+epsilon) for the corresponding flow in A\nand vice versa.\n\nNow let f_a be the min cost flow in A and f_o the min cost flow in O.\nAssume that c(f_o)(1+epsilon)\u003cc(f_a). Then f_o corresponds to a flow\nin A that is cheaper than f_a, but that's impossible because f_a is\nthe min cost flow.\nQED.\n\nProblems might arise anyway because we represent probabilities only\nlogarithmically in the cost, so that a factor of (1+epsilon)\ncorresponds to an exponent (1+epsilon) for the probabilities. But René\nseems optimistic that the resulting flows look good enough in\npractice.\n\nI am still optimistic that exact solvers with something like the cost\nscaling approach might also be feasible (as long as they produce\ninteger flows), but I am happy that this simple approximation approach\nseems good enough. This should save us a lot of work because there are\nmany linear min cost solvers available that represent years of\ncumulative work in optimization research.\n\nCheers\n  Stefan\n\nAm Sa., 19. März 2022 um 22:09 Uhr schrieb Martin via Lightning-dev\n\u003clightning-dev at lists.linuxfoundation.org\u003e:\n\u003e\n\u003e Dear Carsten, Rene and fellow lightning developers,\n\u003e\n\u003e 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:\n\u003e\n\u003e \u003e 8) Quality of Approximation\n\u003e \u003e\n\u003e \u003e There are some problems in computer science that are hard/impossible to\n\u003e \u003e approximate, in the sense that any kind of deviation from the optimum\n\u003e \u003e could cause the computed results to be extremely bad. Do you have some\n\u003e \u003e idea (or proof) that your kind of approximation isn't causing a major\n\u003e \u003e issue? I guess a piece-wise linearization with an infinite number of\n\u003e \u003e pieces corresponds to the optimal result. Given a finite number of\n\u003e \u003e pieces, how large is the difference to the optimum?\n\u003e\n\u003e 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.\n\u003e\n\u003e 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.\n\u003e\n\u003e Cheers,\n\u003e Martin\n\u003e\n\u003e [1] https://arxiv.org/abs/2107.05322\n\u003e [2] https://twitter.com/renepickhardt/status/1502293438498234371\n\u003e [3] https://www.worldscientific.com/doi/abs/10.1142/9789812798190_0005\n\u003e _______________________________________________\n\u003e Lightning-dev mailing list\n\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev"}