Reproduce “Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Shaddin Dughmi, Yusuf Hakan Kalayci, Xinyu Liu

A polyhedral sparsification framework is introduced, enabling the design of near-optimal sparsifiers for stochastic knapsack, multiple knapsack, and generalized assignment problems. The method yields (1 − ϵ)-approximate solutions with query sets whose size is independent of problem dimensions and empirically demonstrates significant speedups for deterministic solvers.

Key insights

  • The polyhedral sparsification framework provides a structurally appropriate measure of redundancy for capacity-constrained problems, extending sparsification theory.
  • Knapsack-type problems, despite their deterministic hardness, admit efficient (1 − ϵ)-approximate sparsifiers whose query set size is independent of the problem's dimensions.
  • Sparsification offers a way to circumvent inherent computational hardness for dense, non-worst-case instances by reducing the search space to pertinent variables.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.