Stefan Richter [ARCHIVE] on Nostr: 📅 Original date posted:2021-08-21 📝 Original message: Hi Zmn! That is some ...
📅 Original date posted:2021-08-21
📝 Original message:
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 <ZmnSCPxj at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210821/02ef209c/attachment.html>;
📝 Original message:
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 <ZmnSCPxj at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210821/02ef209c/attachment.html>;