Timeline for $k$-th subset in order of increasing sum
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 21, 2017 at 7:28 | comment | added | Chao Xu | Output all subset up to the $k$th one is only $O(k \log k)$, because output a set of size $t$ implies all its subsets are also in the output, so the largest set has size $\log k$. | |
| Oct 11, 2016 at 17:15 | comment | added | David Eppstein | Correct, of course. There's still a big gap between hardness for polylog$(k)$ and this $O(k)$ algorithm that it would be interesting to tighten. | |
| Oct 11, 2016 at 14:45 | comment | added | Max Alekseyev | In view of my answer below, please notice that the proposed algorithm is not polynomial in the size of the input. The input size here is a polynomial in $|T|$ and $\log k$ (not $k$). | |
| Nov 1, 2015 at 18:27 | vote | accept | user128409235 | ||
| Nov 1, 2015 at 18:19 | comment | added | David Eppstein | Store the original index of each element before sorting. Use the data structure from the appendix of my paper arxiv.org/abs/1504.04931 to break ties quickly. | |
| Nov 1, 2015 at 2:37 | history | answered | David Eppstein | CC BY-SA 3.0 |