š
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>;
Stefan Richter [ARCHIVE] /
npub19fā¦f4wf0
2023-06-09 12:41:04
in reply to nevent1qā¦j4rw
Author Public Key
npub19fnl48y9j4fk9w0a284mqvszq6fuppelqp2tcxf0s37l95avdtussf4wf0Published at
2023-06-09 12:41:04Event JSON
{
"id": "514f1ae636cfa8c5ff0cdaf412b7886df2e51f3ed8b4f50415e917a44ad984e8",
"pubkey": "2a67fa9c85955362b9fd51ebb032020693c0873f0054bc192f847df2d3ac6af9",
"created_at": 1686314464,
"kind": 1,
"tags": [
[
"e",
"0bce76182bf2be82b4ff2c715e742882c8f230a5677f98725d09f1c7d4c47725",
"",
"root"
],
[
"e",
"b43e79501e8b6ce52195a4a2ed1c0f8dd9b1abc55c1483eb10ebac872bb7aafe",
"",
"reply"
],
[
"p",
"4505072744a9d3e490af9262bfe38e6ee5338a77177b565b6b37730b63a7b861"
]
],
"content": "š
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",
"sig": "5cc76859a43d5be387bab58da71dcf27a241caf6f9bc0f57e3e4d7e8b471458a7389f6e2bdfcec3f02740212599592a18b4fa279cb92d021ff3a1a84a06ec91d"
}