{"type":"rich","version":"1.0","author_name":"npub1gudxspr8gkafq0mvzrwpj5qyuhtr3euwqf08rlkdr63zhe39l30qzplrqg","author_url":"https://nostr.ae/npub1gudxspr8gkafq0mvzrwpj5qyuhtr3euwqf08rlkdr63zhe39l30qzplrqg","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2022-03-19\n📝 Original message:\nDear Carsten, Rene and fellow lightning developers,\n\nRegarding 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\n\u003e 8) Quality of Approximation\n\u003e\n\u003e There are some problems in computer science that are hard/impossible to\n\u003e approximate, in the sense that any kind of deviation from the optimum\n\u003e could cause the computed results to be extremely bad. Do you have some\n\u003e idea (or proof) that your kind of approximation isn't causing a major\n\u003e issue? I guess a piece-wise linearization with an infinite number of\n\u003e pieces corresponds to the optimal result. Given a finite number of\n\u003e pieces, how large is the difference to the optimum?\n\nI 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\nAdmittedly 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\nCheers,\nMartin\n\n[1] https://arxiv.org/abs/2107.05322\n[2] https://twitter.com/renepickhardt/status/1502293438498234371\n[3] https://www.worldscientific.com/doi/abs/10.1142/9789812798190_0005\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220319/f278c153/attachment.html\u003e"}