From: Peter R <peter_r@gmx•com>
To: "bitcoin-dev@lists•linuxfoundation.org Dev"
<bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] Unlimited Max Blocksize (reprise)
Date: Sun, 30 Aug 2015 10:00:37 -0700 [thread overview]
Message-ID: <32D6AD7B-5EA2-4FC3-AB5A-A43C7482F2F9@gmx.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 1129 bytes --]
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
[-- Attachment #2: Type: text/html, Size: 1505 bytes --]
next reply other threads:[~2015-08-30 17:00 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-08-30 17:00 Peter R [this message]
-- strict thread matches above, loose matches on Subject: below --
2015-08-30 11:49 Daniele Pinna
[not found] ` <B52558A9-8897-450B-B386-503773EE0867@gmx.com>
2015-08-30 21:10 ` Tom Harding
[not found] <CAEgR2PEMueQc7GgYWYMOZgtKHvxHgoe1rT1F+YpG2x0h74+_Gw@mail.gmail.com>
[not found] ` <CAEgR2PHnJfCwMzFCrJr_TnFzRjJ7GVE-4=omva92nO6g9z2LSQ@mail.gmail.com>
2015-08-26 22:22 ` Daniele Pinna
2015-08-27 0:48 ` Jorge Timón
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=32D6AD7B-5EA2-4FC3-AB5A-A43C7482F2F9@gmx.com \
--to=peter_r@gmx$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox