Local Computation Algorithm for Integer Packing Problems

Abstract

Local Computation Algorithms (LCA) are sublinear time/space algorithms for search problems. LCA consider the circumstances where both input and output are massive. LCA implement efficient query access to a small portion of a certain valid solution of the underlying problem without computing the whole output. Most previous works on LCAs have focused on graph problems as the existing techniques

rely on locality of the graph structure to reduce instance size to achieve small time and space complexity. It is unclear combinatorial optimization problems such as Knapsack can be solved under the LCA model. We study Knapsack Problem under the LCA model. We have proved that it is impossible to obtain a sublinear time LCA that provides query access consistent with the optimal solution, any finite approximation solution or maximal feasible solution of the input Knapsack instance. We adapted the weighted sampling model and the study of reproducible algorithm to construct an LCA that provides query access consistent with an approximation solution with sublinear sample complexity with probability at 2/3.