[bitcoin-dev] Unlimited Max Blocksize (reprise)

[Peter R]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150830/d1591a5e/attachment.html>