Polynomial-time solvability of integer knapsacks in the diagonal Frobenius cone

Let AA be an integer matrix with columns v1,,vnZm{\boldsymbol v}_1,\ldots,{\boldsymbol v}_n\in\mathbb{Z}^m, let

C={μ1v1++μnvn:μ1,,μn0},C=\{\mu_1{\boldsymbol v}_1+\cdots+\mu_n{\boldsymbol v}_n:\mu_1,\ldots,\mu_n\geq 0\},

and set v=v1++vn{\boldsymbol v}={\boldsymbol v}_1+\cdots+{\boldsymbol v}_n. Let P(A,b)P(A,{\boldsymbol b}) denote the integer knapsack polytope, and let g(A)\mathrm{g}(A) be the diagonal Frobenius number, namely the minimal s0s\geq 0 such that every b(sv+C)Zm{\boldsymbol b}\in(s{\boldsymbol v}+C)\cap\mathbb{Z}^m makes P(A,b)P(A,{\boldsymbol b}) contain an integer point. Polynomial-time solvability conjecture. The problem is solvable in polynomial time for all instances (A,b)(A,{\boldsymbol b}) with

b(g(A)v+C)Zm.{\boldsymbol b}\in(\mathrm{g}(A){\boldsymbol v}+C)\cap\mathbb{Z}^m.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.