Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with -SUM in 2DResearch Paper
In -Knapsack (the vector or multidimensional knapsack problem) every item has a profit and a -dimensional weight vector, and one must choose a set of items of maximum total profit whose total weight stays within a capacity in every coordinate. It models any selection problem with several budgets at once (money, time, space, staff) and is the simplest…