Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them

Clément L. Canonne, Yun Li, Seeun William Umboh

Local Computation Algorithms (LCA), as introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a type of ultra-efficient algorithms which, given access to a (large) input for a…