2026-07-21T14:19:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25338 2026-03-19T13:03:43Z ddc:004 open_access

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems Dughmi, Shaddin Kalayci, Yusuf Hakan Liu, Xinyu Packing Problems Assignment Problems Stochastic Selection Sparsification 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-ε)-approximate sparsifiers with degree polynomial in 1/p and 1/ε - 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 directly 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-ε)-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? Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shaddin Dughmi and Yusuf Hakan Kalayci and Xinyu Liu 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.51 urn:nbn:de:0030-drops-253386 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.51 eng https://creativecommons.org/licenses/by/4.0/legalcode