Timeline for Reference request: how to find the k'th best solution to the 1-0 knapsack problem?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 2, 2015 at 10:52 | comment | added | vkrouglov | Your comment is legitimate and I am not sure how to formally define my question. It is more of a philosophical question - how to find the k'th best solution directly without exploring the full search space or the Top k solutions. For example in the standard approach via dynamic programming we are cutting off big chunks of search space that cannot be in the optimal solution. Is it possible to do the same for the k'th best solution? | |
| Sep 28, 2015 at 21:56 | comment | added | Sidharth Ghoshal | If the complexity didn't depend on k and it was poly time in the size (#of bits) to represent the problem then you would solve P = NP, by setting k = 1, if it truly doesn't impact the running time | |
| Sep 28, 2015 at 10:09 | comment | added | vkrouglov | Polynomial in the size of the problem and faster than linear in k. Ideally, the complexity would not depend on k. | |
| Sep 28, 2015 at 8:06 | comment | added | Sidharth Ghoshal | Are you expecting a poly time result? If not,then many of the traditional techniques such as cutting planes, branch and bound would seem applicable, where eahc is run until the optimal is found and then we trim off the optimal, repeating this k-1 times. | |
| Sep 28, 2015 at 7:41 | history | asked | vkrouglov | CC BY-SA 3.0 |