From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 677A0279 for ; Sun, 30 Aug 2015 17:00:41 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mout.gmx.net (mout.gmx.net [212.227.15.18]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id BCEDE1E8 for ; Sun, 30 Aug 2015 17:00:40 +0000 (UTC) Received: from [192.168.50.29] ([69.50.179.106]) by mail.gmx.com (mrgmx002) with ESMTPSA (Nemesis) id 0LsCdj-1YZ9Hm3O6p-013t9W for ; Sun, 30 Aug 2015 19:00:38 +0200 From: Peter R Content-Type: multipart/alternative; boundary="Apple-Mail=_765913D6-131B-4EA8-9579-2ABAD12D3047" Message-Id: <32D6AD7B-5EA2-4FC3-AB5A-A43C7482F2F9@gmx.com> Date: Sun, 30 Aug 2015 10:00:37 -0700 To: "bitcoin-dev@lists.linuxfoundation.org Dev" Mime-Version: 1.0 (Mac OS X Mail 6.6 \(1510\)) X-Mailer: Apple Mail (2.1510) X-Provags-ID: V03:K0:Qpla54Uuo41qk6fC+5nWafemtyhpkr9osqKs02o1gBij4+qtnpf vJRs4LeWrZoWLJYjhglrtcfYJ7WFDMnYl3ilPnZD1dkrSG/wCJWwiKW9jaWjsBGEgs/teWk Uthuv2dXJg4nD6p4nq7QAq4j3PRYHqlOvqZc5PXlkettWFyPRYKzy7AtXCt371L80wxZlrv yK1UgCYCfk9uHPHPX39Ew== X-UI-Out-Filterresults: notjunk:1;V01:K0:u7Skr1+o1rk=:O/CpxJRoVZgbIfXj4AOsse 5A7ntw1JK9DAZvNYFiCRR1hYRiVsh2qUOWmZ2nJqJ2v/FaW0cYOBFlIb4U3+aGyrXvXjli9o5 +2z0cTD8ZWe6SYkKMautPWWgRs2aEM8IoyOK2i1sG4n6lWgSlB18Os3DO2NfRz84cAIMiFBZt sYxr9xKIwCtNzSR9vjp8YEDbpMb2aHdKa5pvUS7sPxLnzuWKywkJV6YYty4dPj+Njy4gzS98C Bb6FmMnr7MlPOAtrG1pp6QQ76jz1vM9LQMaVD1yksXkyqJaK9xE2cMaQ4zWaD7ZsOBcq9VKG9 t4+CEO6ly/cKDFJTtvdOKnGHBuYGcqp+CU5sm08SWuY8nKHlgePc6FGFCqW6/XmOoalrin5ri 2Df/rKrxPK/Ehbx+fBiCOEI8olleeddXrh/tVdFtO3dZ4j8dfguy4xvtncFptta2qxANr0TCu Fm0xewtyDhedRfv4zCqEwoThNDo765h+DyGNPOLHJ1Msz3/YosQsnwr2uZZyKlkkzNlLXQeCd GB62tAv0Ho9LwiccJB9brmLzvxcdgeb2Os+bQL4fwC2OpZXnY1WDkfI99sMg2tZ3v5x2Rcf8n BLVzOX8HKi7685W7YCPtZFFfi/VFUasMll7SSRm5xXj8V0FaDZ4/YatxvdxvXPvR7wco+cQAC OU1TNypBraztF5z4g/+wclUWn9u7ZA4SAHSLoWCM8os07HHZqx6/85RXweefrUO2Gynhl55Mz pQs+1bMVGz0jmjRjJWwCETlqNlrpYH0WM6XCtc8zqb3JwA8zzIhw3HMwkyI7I+Dbzh/wpkt1F NxrtmLWKfkSP8mix5dzpm17s1pMWNV4XIvBALnFWkabfu7HTtw= X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,FREEMAIL_FROM, HTML_MESSAGE,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [bitcoin-dev] Unlimited Max Blocksize (reprise) X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 30 Aug 2015 17:00:41 -0000 --Apple-Mail=_765913D6-131B-4EA8-9579-2ABAD12D3047 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii 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. =20 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= --Apple-Mail=_765913D6-131B-4EA8-9579-2ABAD12D3047 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=us-ascii 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
= --Apple-Mail=_765913D6-131B-4EA8-9579-2ABAD12D3047--