Timeline for $k$-th subset in order of increasing sum
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 11, 2016 at 15:16 | history | edited | Max Alekseyev | CC BY-SA 3.0 |
added 91 characters in body
|
| Oct 11, 2016 at 14:20 | comment | added | Max Alekseyev | @D.W.: First, the question does not explicitly ask "for an algorithm whose running time is polynomial in $k$" (such algorithm would not be necessarily polynomial in the size of the input). Second, I proved that if there is a polynomial-time algorithm (in the size of the input, which is polynomial in $\log k$, not $k$), then there would be one for the subset sum problem. Third, the algorithm proposed in the other answer is not polynomial as it constructs a tree on all subsets of the input set. | |
| Nov 1, 2015 at 13:06 | history | edited | Max Alekseyev | CC BY-SA 3.0 |
link and more details
|
| Nov 1, 2015 at 7:21 | history | edited | Max Alekseyev | CC BY-SA 3.0 |
added 35 characters in body
|
| Nov 1, 2015 at 7:15 | history | answered | Max Alekseyev | CC BY-SA 3.0 |