Hello Tom, Daniele --
Thank you Tom for pointing out the knapsack problem to all of us. I will
include a note about it when I make the other corrections to the Fee Market
paper.
I agree with what Daniele said previously. The other "non-greedy" solutions to
the knapsack problem are most relevant when one is choosing from a smaller
number of items where certain items have a size similar to the size of the
knapsack itself. For example, these other solutions would be useful if
transactions were often 50 kB, 100 kB, 400 kB in size, and we were trying to
find the optimal TX set to fit into a 1 MB block.
However, since the average transaction size is ~500 bytes, even with a block
size limit of 1 MB, we are looking at up to 2000 transactions. The
quantization effects become small. Rather than 22 triangles as shown in Fig. 3
(http://imgur.com/rWxZddg), there are hundreds or a few thousands, and we can
reasonably approximate the discrete set of points as a continuous curve. Like
Daniele pointed out, the greedy algorithm assumed in the paper is
asymptotically optimal in such a case.
Best regards,
Peter
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
