An FPTAS for the Δ-modular multidimensional knapsack problem
share
It is known that there is no EPTAS for the m-dimensional knapsack problem unless W[1] = FPT. It is true already for the case, when m = 2. But, an FPTAS still can exist for some other particular cases of the problem. In this note, we show that the m-dimensional knapsack problem with a Δ-modular constraints matrix admits an FPTAS, whose complexity bound depends on Δ linearly. More precisely, the proposed algorithm complexity is O(T_LP· (1/ε)^m+3· (2m)^2m + 6·Δ), where T_LP is the linear programming complexity bound. In particular, for fixed m the arithmetical complexity bound becomes O(n · (1/ε)^m+3·Δ). Our algorithm is actually a generalisation of the classical FPTAS for the 1-dimensional case. Strictly speaking, the considered problem can be solved by an exact polynomial-time algorithm, when m is fixed and Δ grows as a polynomial on n. This fact can be observed combining previously known results. In this paper, we give a slightly more accurate analysis to present an exact algorithm with the complexity bound O(n ·Δ^m + 1), for m being fixed. Note that the last bound is non-linear by Δ with respect to the given FPTAS.
READ FULL TEXT