tag:blogger.com,1999:blog-4147841314301981805.post8160946400488827896..comments2023-03-26T07:38:56.925-06:00Comments on Heisencoder: iDrone reprint: Thoughts on the Subset Sum ProblemMatthew V Ballhttp://www.blogger.com/profile/04512577643269096659noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-4147841314301981805.post-9936049725611088972010-06-04T11:42:12.275-06:002010-06-04T11:42:12.275-06:00Anonymous: Unfortunately, I don't know about ...Anonymous: Unfortunately, I don't know about current benchmarks for the subset problem. Specific implementation is less the focus of this article, and more about the overall "Big-O" complexity for solving the problem. <br /><br />How does your code scale when doubling from 300 to 600 positive integers? I'd be very interested in whether it scales gracefully in this situation.Matthew V Ballhttps://www.blogger.com/profile/04512577643269096659noreply@blogger.comtag:blogger.com,1999:blog-4147841314301981805.post-34040366729056396432010-06-04T05:31:28.913-06:002010-06-04T05:31:28.913-06:00hi Mathew,
I wrote an algorithm in Java that solv...hi Mathew,<br /><br />I wrote an algorithm in Java that solves that finds the subset from a set of 300 positive random integers in the range of 10^14 to 10^15, after taking about a minute on my old XP laptop. The target sum is about 10^17.<br /><br />Do you think these results worth comparing with known results? Do you know of any current benchmarks? I'm just trying to know where my algorithm's performance stands in comparison with the known algos.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4147841314301981805.post-69301247334735278612008-03-05T15:57:00.000-07:002008-03-05T15:57:00.000-07:00I think the question is whether this 'rectangle su...I think the question is whether this 'rectangle subset sum' problem is NP-complete -- like the subset sum problem. That is to say, does the complexity of finding a solution in the general case increase in a manner similar to that of the Subset Sum problem.<BR/><BR/>In the rectangle variant, finding the target sum is straightforward:<BR/><BR/>target sum = total sum / k<BR/><BR/>We need a criterion for deciding whether we achieved the 'closest' solution. I think the easiest way would be to sum the absolute value of the errors (i.e., the difference between the actual sum and the target sum) for all the rectangles, then minimize that value.<BR/><BR/>If the problem was then to find a single grouping of elements that most closely sums to the target sum, I think this would be the subset sum problem.<BR/><BR/>However, the requirement of tiling 'k' rectangles over the grid of cells significantly reduces the possible configurations -- there are a limited number of ways to tile rectangles. Because of that restriction, I suspect the rectangle version's complexity doesn't grow as fast as for the subset sum problem, but I don't know whether it grows polynomially or exponentially as the grid size increases.<BR/><BR/>Let's take the case of k = 2 rectangles for an n by n grid. In this case, there are 2(n-1) ways to tile two rectangles onto the grid (split either horizontally or vertically, and the first rectangle can have between 1 and n-1 widths -- n-1 because the second rectangle needs at least a width of 1). In this case the complexity of finding the optimal solution is about O(n^2) -- it takes 2(n^2) operations to sum all the rows and columns, and testing for the optimal split afterwards takes linear time.<BR/><BR/>So, for k = 2, this is not an NP-complete problem. For larger k, I don't know how the complexity increases, but I suspect it's not exponential.<BR/><BR/>Given this back-of-the-napkin analysis, I suspect that this 'rectangle' problem is not in the same complexity class as the subset sum problem, but it's quite possible that the total rectangle groupings grows exponentially for large k.Matthew V Ballhttps://www.blogger.com/profile/04512577643269096659noreply@blogger.comtag:blogger.com,1999:blog-4147841314301981805.post-75168140384972175072008-03-04T08:33:00.000-07:002008-03-04T08:33:00.000-07:00I was wondering whether the problem I am handling ...I was wondering whether the problem I am handling right now is a variant of the subset sum problem<BR/><BR/>There is a 7 by 7 grid of cells, each containing a number.<BR/>Find the set of k nonoverlapping rectangles(max k is 10) that together completely cover the grid<BR/>such that the sum of the numbers inside each rectangle<BR/>are all equal or most nearly equal ?<BR/><BR/>e.g. let the sum of all numbers in the 7*7 grid is 2000. assume K is 4<BR/>then ideal solution is 4 rectangles each with 500. But this<BR/>is not possible as numbers may not exactly sum to 500<BR/>for some rectangle/s. So solution can be for example<BR/>503,497,500,500.<BR/>For the same grid if k = 5, ideal is 5 rectangles each 400. But may be the<BR/>best soln is 401,402,400,399,398.<BR/><BR/>Any thoughts ? comments ?Anonymousnoreply@blogger.com