Timeline for Two versions of Subset Sum Problem
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2020 at 13:31 | vote | accept | kanso37 | ||
| Feb 19, 2020 at 2:30 | answer | added | Yuval Filmus | timeline score: 3 | |
| Feb 19, 2020 at 0:00 | comment | added | kanso37 | What a clever technique! Thanks. | |
| Feb 18, 2020 at 23:17 | comment | added | Yuval Filmus | Right. Let’s assume $W-k=2^t$. Add weights $1,2,4,\dots,2^{t-1}$, and ask for a target of $W$. Perhaps a similar approach can be used in general. | |
| Feb 18, 2020 at 23:13 | comment | added | kanso37 | @YuvalFilmus Thanks for the response! I understand now how to reduce the second to the first. But as for reducing the first to the second: It seems like you would run into trouble since you only want to know if there is a subset with weight at least some number $k$. Wouldn't checking all numbers from $k$ to $W$ using the second be exponential because it depends on the magnitude of the numbers? | |
| Feb 18, 2020 at 15:55 | comment | added | Yuval Filmus | Reduce the second to the first by taking $k=W$. The other direction is direct (verify first that $k \le W$). | |
| Feb 18, 2020 at 14:05 | history | edited | xskxzr |
edited tags
|
|
| Feb 17, 2020 at 21:07 | history | asked | kanso37 | CC BY-SA 4.0 |