Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
Shaddin Dughmi, Yusuf Hakan Kalayci, Xinyu Liu · 2025
Read Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems by Shaddin Dughmi, Yusuf Hakan Kalayci, Xinyu Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-01240.txt.
Introduction
Shaddin Dughmi, Yusuf Kalayci, and Xinyu Liu study choice under doubt with costly checks. In packing tasks, each item has an unknown gain. Checking an item costs time or money. The key choice is which few items to check first.
Their work looks for sparse sets that still lead to near-best plans. Past work scored sparsity by how many items were checked. The team seeks sets that come close to the best score with few checks. Good sparse sets save cost in tasks like hiring, ads, and stock choice, where each check has a real price.
Catalog record
| CREATOR | Shaddin Dughmi, Yusuf Hakan Kalayci, Xinyu Liu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-01240
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems Shaddin Dughmi, Yusuf Hakan Kalayci, Xinyu Liu 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 − ϵ ) (1-\epsilon) -approximate sparsifiers with degree polynomial in 1 / p 1/p and 1 / ϵ 1/\epsilon – where p 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 − ϵ ) (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? 1 Introduction The sparsification of stochastic packing problems has emerged as a fundamental paradigm for designing algorithms that achieve near-optimal solutions with limited access to uncertain data. This approach proves particularly valuable in settings where probing or querying elements incurs costs or faces constraints. Recent developments in sparsification of stochastic packing problems have revealed elegant techniques for selecting the most pertinent information to probe. Our goal in this paper is to expand the sparsification toolbox beyond well-studied matching settings [ 1 , 3 , 5 , 7 , 6 , 8 , 9 , 14 , 15 , 29 ] and matroid optimization problems [ 16 , 23 , 29 ] to design sparsifiers for knapsack-type constraints. A detailed survey of related work appears later in Section 7.1 . We adopt the general framework of Dughmi et al. [ 16 ] for a packing problem instance \langle E,\mathcal{F},f\rangle , where E is a ground set of elements, \mathcal{F}\subseteq 2^{E} is a downward-closed family of feasible sets, and f:2^{E}\to\mathbb{R}_{\geq 0} is an objective function. In our stochastic setting, each element e\in E becomes active independently with probability p\in(0,1] , resulting in a random active set R\subseteq E . A sparsification algorithm selects a query set Q\subseteq E prior to observing R , aiming to maximize the solution value within the revealed subset Q\cap R . For assignment problems like MKP and GAP, solutions are typically defined as sets of item-knapsack pairs (assignments) rather than simple subsets of items. To align with our sparsification framework, we project these problems onto the ground set of items E . We say a subset of items S\subseteq E is feasible ( S\in\mathcal{F} ) if there exists a valid assignment of items in S to knapsacks that respects all capacity constraints. Accordingly, we extend the objective function to item sets by defining f(S) as the maximum value achievable by any feasible assignment of the items in S . To rigorously evaluate sparsification algorithms, we must balance approximation quality against the “size” of the query set. While approximation is defined as usual, quantifying the size of Q for knapsack-type problems requires nuance. Traditional cardinality-based measures – which normalize |Q| by the rank of \mathcal{F} – fail when feasible sets vary dramatically in size, as in capacity-constrained problems. To address this, we introduce the polyhedral sparsification degree . Let \mathcal{P}_{\mathcal{F}}=\operatorname{conv}(\{\mathbf{1}_{S}:S\in\mathcal{F}\}) be the polytope of feasible solutions. We define the degree of a query set Q as the minimum scalar d\geq 1 such that the normalized indicator vector \frac{1}{d}\mathbf{1}_{Q} lies within \mathcal{P}_{\mathcal{F}} . This definition naturally generalizes existing notions 1 1 1 Sparsification in stochastic integer packing was introduced by Blum et al. [ 9 ] using vertex degree, and later generalized by Maehara and Yamaguchi [ 23 , 29 ] to cardinality-based measures. by capturing the intuitive notion of redundancy: a query set has degree d if it can be decomposed into d (fractionally) feasible solutions. Definition 1 (Sparsifier) . An algorithm \mathcal{A} is an \alpha -approximate sparsifier with degree d if, for every problem instance, it returns a (possibly randomized) query set Q\subseteq E that satisfies two conditions: 1. Polyhedral Feasibility: the indicator vector of the query set lies within the polytope scaled by d , in other words \frac{1}{d}\cdot\mathbf{1}_{Q}\in\mathcal{P}_{\mathcal{F}} (holding for every realization of Q ); 2. Approximation Guarantee: the expected value of the optimal solution within the queried active elements approximates the full-information optimum, such that \mathbb{E}_{R,Q}[\mathop{max}\{f(S):S\in\mathcal{F}\cap 2^{Q\cap R}\}]\geq\alpha\cdot\mathbb{E}_{R}[\OPT]. Our contributions. Our main result establishes that knapsack-type problems admit effective sparsification despite their computational hardness. We design deterministic and non-adaptive algorithms that produce (1-\epsilon) -approximate sparsifiers with polyhedral degree polynomial in 1/p and 1/\epsilon , remarkably independent of the number of items or constraints. Unlike some prior work [ 23 , 29 ] , we require our degree to be independent of the total number of variables and constraints. 2 2 2 To be clear, our definition of degree implicitly allows the number of queries to scale with the cardinality of a typical solution. Our pursuit of constant degree (independent of the number of items or constraints) is akin to requiring “redundancy” on the order of a constant number of solutions, as a hedge against uncertainty. Informal Theorem (Main Result) . For parameters \epsilon\in(0,1/6) and p\in(0,1] , there exist efficient algorithms that produce a (1-O(\epsilon)) -approximate sparsifier for the stochastic Knapsack, Multiple Knapsack, and Generalized Assignment Problems with sparsification degree \text{poly}(1/\epsilon,1/p) . For the single knapsack problem, our approach employs a bucketization strategy combined with a charging argument. Items are partitioned into buckets based on value, and each bucket is filled to approximately \text{poly}(1/p,1/\epsilon) times the knapsack capacity. This redundancy allows for a substitution mechanism: if an optimal item is not queried, it can likely be replaced by a queried item from the same bucket. Feasibility is maintained by prioritizing items with smaller weights, with a refined density-based strategy for the smallest value bucket. Extending this to the Generalized Assignment Problem (GAP) presents a fundamental obstacle: item characteristics are knapsack-dependent, breaking the direct substitutability essential to the single knapsack case. An item ideal for one knapsack may be highly inefficient for another. We overcome this by increasing redundancy – filling buckets to \text{poly}(1/p,1/\epsilon)\cdot(1/\epsilon) capacity – and developing a sophisticated charging argument. When an optimal item cannot be directly substituted (often because potential substitutes are assigned elsewhere), we fractionally distribute its lost value across multiple queried elements. This ensures that we recover nearly the full optimal value without overburdening any specific element in the analysis.