Hi Zmn! That is some amazing lateral thinking you have been applying there. I'm quite certain I haven't understood everything fully, but it has been highly entertaining to read. Will have to give it a closer read when I get some time.
As a first impression, here are some preliminary observations: While I highly like the Haskell-style datatype, and the algorithm we use does mostly use Dijkstra pathfinding, I think what is really important in your definition is the computeCost definition. This is what we would call the cost function IIUC, and in order to be able to solve min-cost flow problems it generally has to be separable and convex. I believe your datatype merely hides the fact that it is neither. Intuitively, I think that any cost function that implies a fixed cost (that is, independent of the amount, though it might be different for every edge) per edge is concave and in theory problematic for min-cost flow algorithms because you could reduce some kind of NP-hard selection problem to it. I believe that applies to most if not all of your ideas in the text. Again, I think we should think more about how much of a problem that is in practice, because we do have tools like approximation and parameterized algorithms, as well as heuristics, and I also believe that, say, a moderate base fee will not change the optimal flow much, because this will always prefer large Htlcs anyway in order to optimize probability. I am really grateful that you have been taking the time to read and understand our paper and have been thinking further in this fascinating way. I am certain good things will come of it in time. Cheers, Stefan ZmnSCPxj <zmnsc...@protonmail.com> schrieb am Sa., 21. Aug. 2021, 03:49: > > > Alternative Pathfinding? > > ======================== > > > Or to put this section more succinctly: Why should cost be a number? > > What operations do the minimum cost flow algorithms demand of this thing > called "cost", and can we provide those operations using something which is > not a number but is instead a different structure? > What is the minimal interface that the mincostflow algo demands of this > "cost" datatype? > > Regards, > ZmnSCPxj >
_______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
