How do I find the k'th best solution to the 1-0 knapsack problem without finding the Top-k solutions? Is there any mathematical research that deals with the k'th best solutions to the mixed integer programming problems?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ 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. $\endgroup$– Sidharth GhoshalCommented Sep 28, 2015 at 8:06
-
$\begingroup$ Polynomial in the size of the problem and faster than linear in k. Ideally, the complexity would not depend on k. $\endgroup$– vkrouglovCommented Sep 28, 2015 at 10:09
-
$\begingroup$ 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 $\endgroup$– Sidharth GhoshalCommented Sep 28, 2015 at 21:56
-
$\begingroup$ 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? $\endgroup$– vkrouglovCommented Oct 2, 2015 at 10:52
Add a comment
|