{"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:2021-08-21\n📝 Original message:\nHi Zmn! That is some amazing lateral thinking you have been applying there.\nI'm quite certain I haven't understood everything fully, but it has been\nhighly entertaining to read. Will have to give it a closer read when I get\nsome time.\n\nAs a first impression, here are some preliminary observations: While I\nhighly like the Haskell-style datatype, and the algorithm we use does\nmostly use Dijkstra pathfinding, I think what is really important in your\ndefinition is the computeCost definition. This is what we would call the\ncost function IIUC, and in order to be able to solve min-cost flow problems\nit generally has to be separable and convex. I believe your datatype merely\nhides the fact that it is neither.\n\nIntuitively, I think that any cost function that implies a fixed cost (that\nis, independent of the amount, though it might be different for every edge)\nper edge is concave and in theory problematic for min-cost flow algorithms\nbecause you could reduce some kind of NP-hard selection problem to it. I\nbelieve that applies to most if not all of your ideas in the text. Again, I\nthink we should think more about how much of a problem that is in practice,\nbecause we do have tools like approximation and parameterized algorithms,\nas well as heuristics, and I also believe that, say, a moderate base fee\nwill not change the optimal flow much, because this will always prefer\nlarge Htlcs anyway in order to optimize probability.\n\nI am really grateful that you have been taking the time to read and\nunderstand our paper and have been thinking further in this fascinating\nway. I am certain good things will come of it in time.\n\nCheers,\n  Stefan\n\nZmnSCPxj \u003cZmnSCPxj at protonmail.com\u003e schrieb am Sa., 21. Aug. 2021, 03:49:\n\n\u003e\n\u003e \u003e     Alternative Pathfinding?\n\u003e \u003e     ========================\n\u003e\n\u003e\n\u003e Or to put this section more succinctly: Why should cost be a number?\n\u003e\n\u003e What operations do the minimum cost flow algorithms demand of this thing\n\u003e called \"cost\", and can we provide those operations using something which is\n\u003e not a number but is instead a different structure?\n\u003e What is the minimal interface that the mincostflow algo demands of this\n\u003e \"cost\" datatype?\n\u003e\n\u003e Regards,\n\u003e ZmnSCPxj\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210821/02ef209c/attachment.html\u003e"}