Polynomial-time solvability of integer knapsacks in the diagonal Frobenius cone
Polynomial-time solvability of integer knapsacks in the diagonal Frobenius cone
Let be an integer matrix with columns , let
and set . Let denote the integer knapsack polytope, and let be the diagonal Frobenius number, namely the minimal such that every makes contain an integer point. Polynomial-time solvability conjecture. The problem is solvable in polynomial time for all instances with
The feasible translated cone guarantees that the knapsack polytope contains an integer point for every right-hand side in the specified region, and the conjecture asks whether this structural promise yields a polynomial-time algorithm. The source provides no resolution, so the conjecture remains open.
Sources & referencesView supporting material
Primary source
Iskander Aliev and Martin Henk, “LLL-reduction for Integer Knapsacks”, arXiv:1012.3182 (2011).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.