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

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

TL;DR

This paper proves that it is mathematically impossible to build a standard Local Computation Algorithm (LCA) for the Knapsack problem—even for rough approximations. However, the authors show that by giving the algorithm a "weighted sampling" superpower and borrowing "reproducibility" techniques from machine learning, we can achieve a $(1/2 + \epsilon)$-approximation with nearly constant query complexity.

What Problem Does This Paper Address?

The Knapsack problem is a cornerstone of combinatorial optimization: given a set of items with weights and profits, how do you fill a knapsack to maximize profit without exceeding a weight limit?

In the era of massive data, we often use Local Computation Algorithms (LCAs). Imagine a huge dataset distributed across a thousand servers. An LCA allows each server to answer "Is item $i$ in the optimal solution?" quickly and independently. Crucially, all servers must be consistent (agreeing on the same global solution) without talking to each other or storing a shared state.

The challenge is the "needle in a haystack" problem. If an algorithm only looks at a tiny, sublinear fraction of the items, how can it possibly know if item $i$ belongs in a globally optimal—or even just a "good"—solution?

Methods

The paper is divided into two parts: "The Bad News" (impossibility) and "The Good News" (the workaround).

  1. Lower Bounds (The Bad News): The authors use reductions from communication and query complexity (specifically the OR function) to prove that in the standard model, any LCA for Knapsack must essentially read the entire input.
  2. Weighted Sampling (The Workaround): To bypass the impossibility, they adopt a model where the algorithm can sample items with probability proportional to their profit. This allows the algorithm to "find" the most important items quickly.
  3. Reproducibility: The biggest hurdle for LCAs is consistency. If two independent queries use different random samples, they might calculate different "efficiency thresholds" and give contradictory answers. To fix this, the authors adapt the concept of reproducibility from learning theory. They develop a "reproducible quantile" algorithm that ensures different runs converge on the same thresholds with high probability.

Datasets

As a theoretical computer science paper, no empirical datasets were used. The results are proven mathematically for any valid Knapsack instance.

Key Insights and Ideas

  • Standard Querying is Too Weak: In the standard model, an item's profit and weight are independent of its index. Without a way to "zoom in" on high-profit items, an LCA is blind to the global structure.
  • The LCA-Reproducibility Bridge: This is the paper's most novel conceptual contribution. The authors realized that the "consistency" requirement of LCAs is essentially the same as "reproducibility" in machine learning (where an algorithm should output the same model even if trained on different samples from the same distribution).
  • The Power of $\log^* n$: The algorithm's complexity involves the iterated logarithm ($\log^* n$), which grows so slowly that for all practical purposes (like the number of atoms in the universe), it is a small constant. This comes directly from the reproducible median techniques used to stabilize the algorithm.

Key Results

  • Impossibility Theorems: The authors prove there is no sublinear-time LCA for:
  • Finding an optimal solution.
  • Finding an $\alpha$-approximate solution (for any $\alpha > 0$).
  • Finding a maximal feasible solution (a solution where you can't add any more items).
  • The Positive Result: With weighted sampling access, they provide an LCA that:
  • Achieves a $(1/2 + \epsilon)$-approximation.
  • Has a query complexity of $(1/\epsilon)^{O(\log^* n)}$.
  • Remains parallelizable and query-order oblivious.

Limitations and Future Work

  • The $\log^* n$ Factor: While tiny, the dependence on the instance size $n$ via the iterated logarithm is a theoretical blemish. The authors wonder if a truly constant-time (independent of $n$) algorithm exists.
  • Approximation Ratio: The current algorithm provides a $1/2$-approximation (plus $\epsilon$). In classical settings, Knapsack admits a Fully Polynomial Time Approximation Scheme (FPTAS). Whether an LCA can achieve a $(1-\epsilon)$-approximation remains an open question.
  • Broader Applications: The authors suggest that the connection between LCAs and reproducible learning could be a "fruitful direction" for solving other combinatorial problems that currently seem impossible in the local computation model.

Summary updated

BibTeX
@inproceedings{canonne2025local,
  author = {Clément L. Canonne and Yun Li and Seeun William Umboh},
  title = {{Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them}},
  booktitle = {APPROX/RANDOM},
  year = {2025},
  doi = {10.4230/lipics.approx/random.2025.45},
}
Figure