Abstract:There has been a growing interest in studying online stochastic packing and combinatorial allocation under more general correlation structures, motivated by the complex data sets and models driving modern applications. Several past works either assume correlations are weak or have a particular structure, have a complexity scaling with the number of Markovian ``states of the world" (which may be exponentially large in the case of full history dependence), scale poorly with the horizon $T$, or make additional continuity assumptions. We show that for all $\epsilon$, the online stochastic packing (combinatorial allocation) linear programming problem with general correlations (suitably normalized and with sparse columns) has an approximately optimal policy (with optimality gap $\epsilon T$) whose per-decision runtime scales as the time to simulate a single sample path of the underlying stochastic process (assuming access to a Monte Carlo simulator), multiplied by a constant independent of the horizon or number of Markovian states. We derive analogous results for network revenue management (also with flexible products), and online bipartite matching and independent set in bounded-degree graphs, by rounding. Our algorithms implement stochastic gradient methods in a novel on-the-fly/recursive manner for the associated massive deterministic-equivalent linear program.
From: David Goldberg [view email]
[v1]
Tue, 19 Aug 2025 02:32:39 UTC (71 KB)
[v2]
Sat, 30 Aug 2025 17:46:51 UTC (72 KB)
[v3]
Wed, 26 Aug 2026 18:00:30 UTC (85 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。