Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
Preprint
Abstract
When uncertainty meets costly information gathering, a fundamental question emerges: which data points should we probe to unlock near-optimal solutions? Sparsification of stochastic packing problems addresses this trade-off. The existing notions of sparsification measure the level of sparsity, called degree, as the ratio of queried items to the optimal solution size. While effective for matching and matroid-type problems with uniform structures, this cardinality-based approach fails for knapsack-type constraints where feasible sets exhibit dramatic structural variation. We introduce a polyhedral sparsification framework that measures the degree as the smallest scalar needed to embed the query set within a scaled feasibility polytope, naturally capturing redundancy without relying on cardinality. Our main contribution establishes that knapsack, multiple knapsack, and generalized assignment problems admit (1 - epsilon)-approximate sparsifiers with degree polynomial in 1/p and 1/epsilon -- where p denotes the independent activation probability of each element -- remarkably independent of problem dimensions. The key insight involves grouping items with similar weights and deploying a charging argument: when our query set misses an optimal item, we either substitute it with a queried item from the same group or leverage that group's excess contribution to compensate for the loss. This reveals an intriguing complexity-theoretic separation -- while the multiple knapsack problem lacks an FPTAS and generalized assignment is APX-hard, their sparsification counterparts admit efficient (1 - epsilon)-approximation algorithms that identify polynomial-degree query sets. Finally, we raise an open question: can such sparsification extend to general integer linear programs with degree independent of problem dimensions?Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Set Selection Under Explorable Stochastic Uncertainty via Covering Techniques2023
- Stochastic Weighted Matching: (1-ϵ) Approximation2020
- On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAPSIAM Journal on Computing, 2010
- Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e2006
- Complexity of approximating bounded variants of optimization problemsTheoretical Computer Science, 2005
- Knapsack Problems2004
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- A variable depth search algorithm with branching search for the generalized assignment problemOptimization Methods and Software, 1998
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- Reducibility among Combinatorial Problems1972