Timeline for Algorithms for Sorting Subset Sums

4 events

when toggle format	what		by	license	comment
Mar 29, 2016 at 14:17	vote	accept	Manfred Weis
Mar 28, 2016 at 8:32	comment	added	Manfred Weis		Another observation is, that the complexity of generating the subset sums in sorted order isn't $O(n2^n)$ as would follow from sorting the sequence of subset sums, but rather $O(2^n)$ and I wonder, if that would lead to a better complexity estimate of the Horowitz and Sahni algorithm. At least it indicates that the naive complexity bound for subset sum sorting is wrong by a factor of $log(m)$ with $m:=2^n$
Mar 28, 2016 at 8:18	comment	added	Manfred Weis		Prior to finding the solution sketched in my answer, I thought that negative weights would make a difference; that was because I had thought about adding a constant value to the element weights, but not about adding the value to the subsets sums. But still the idea of adding a constant to the subset sums only works for finite sets, whereas the sketched solution also works for infinite sets with no restrictions on element weights and, it also allows one to find a pair subsets of equal weight in finite time in that case, but of course, it can't prove the absence of such a pair.
Mar 28, 2016 at 6:44	history	answered	David Eppstein	CC BY-SA 3.0