Online Allocation with Unknown Shared Supply

• URL: http://arxiv.org/abs/2605.07080v1
• Date: Fri, 08 May 2026 00:59:11 GMT
• Title: Online Allocation with Unknown Shared Supply
• Abstract summary: We study a stateful online model in which a central hub allocates a finite, unknown supply to multiple sites facing sequential demand.<n>Unlike classical make-to-stock or make-to-order inventory models, OSSA precludes backlogging and replenishment only hedges against future demand.<n>We show that GPA achieves the offline optimum up to an additive term independent of the total supply.
• Score: 31.55000083809067
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many real-world resource allocation systems, such as humanitarian logistics and vaccine distribution, must preposition limited supply across multiple locations before demand is realized while stockouts incur irreversible service losses. To study this, we introduce the Online Shared Supply Allocation (OSSA) problem, a stateful online model in which a central hub allocates a finite, unknown supply to multiple sites facing sequential demand under fixed-charge transportation costs and lost-sales penalties. Unlike classical make-to-stock or make-to-order inventory models, OSSA precludes backlogging and replenishment only hedges against future demand. To tackle OSSA, we propose a deterministic threshold-proportional policy GPA and prove that it achieves a $4/3$-approximation to the offline optimum up to an additive term independent of the total supply. We complement this with matching lower bounds showing that the $4/3$ ratio is tight and that the additive-error dependence is unavoidable, even for randomized algorithms that know the total supply upfront. Finally, we develop a learning-augmented extension to GPA that principally incorporates imperfect forecasts (e.g., from human experts or ML models) commonly available in practice, enabling us to exploit high-quality advice while being robust against arbitrary bad ones. Synthetic and real-world experiments show that GPA outperforms natural baselines with global supply is scarce.

Related papers

• A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming [29.531157410826825]
  We study nonstationary Online Linear Programming (OLP)<n>In OLP, $n$ orders arrive sequentially with reward-resource consumption pairs that form a sequence of independent, but not necessarily identically distributed, random vectors.<n>We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments.
  arXiv  Detail & Related papers  (2026-03-15T23:59:30Z)
• Online Linear Programming with Replenishment [9.214452378957697]
  We study an online linear programming (OLP) model in which inventory is not provided upfront but instead arrives gradually through a replenishment process.<n>The introduction of dispersed, uncertain replenishment fundamentally alters the structure of classical OLPs.<n>We develop new algorithms and regret analyses for three major distributional regimes studied in the OLP literature.
  arXiv  Detail & Related papers  (2026-01-21T04:09:29Z)
• Spatial Supply Repositioning with Censored Demand Data [10.797160099834306]
  We consider a network inventory system motivated by one-way, on-demand vehicle sharing services.<n>Finding an optimal policy in such a general inventory network is analytically and computationally challenging.<n>Our work highlights the critical role of inventory in the viability of shared mobility businesses.
  arXiv  Detail & Related papers  (2025-01-31T15:16:02Z)
• A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints [54.46126953873298]
  We address the problem of dynamically pricing complementary items that are sequentially displayed to customers. Coherent pricing policies for complementary items are essential because optimizing the pricing of each item individually is ineffective. We empirically evaluate our approach using synthetic settings randomly generated from real-world data, and compare its performance in terms of constraints violation and regret.
  arXiv  Detail & Related papers  (2024-07-08T09:55:31Z)
• CoSDA: Continual Source-Free Domain Adaptation [78.47274343972904]
  Without access to the source data, source-free domain adaptation (SFDA) transfers knowledge from a source-domain trained model to target domains. Recently, SFDA has gained popularity due to the need to protect the data privacy of the source domain, but it suffers from catastrophic forgetting on the source domain due to the lack of data. We propose a continual source-free domain adaptation approach named CoSDA, which employs a dual-speed optimized teacher-student model pair and is equipped with consistency learning capability.
  arXiv  Detail & Related papers  (2023-04-13T15:53:23Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  We consider an online allocation problem subject to lower and upper resource constraints, where the requests arrive sequentially. We propose a new algorithm that obtains $1-O(fracepsilonalpha-epsilon)$ -competitive ratio for the offline problems that know the entire requests ahead of time.
  arXiv  Detail & Related papers  (2021-12-28T02:21:06Z)
• Improving Self-supervised Learning with Automated Unsupervised Outlier Arbitration [83.29856873525674]
  We introduce a lightweight latent variable model UOTA, targeting the view sampling issue for self-supervised learning. Our method directly generalizes to many mainstream self-supervised learning approaches.
  arXiv  Detail & Related papers  (2021-12-15T14:05:23Z)
• Fairer LP-based Online Allocation [13.478067250930101]
  We consider a Linear Program (LP)-based online resource allocation problem where a decision maker accepts or rejects incoming customer requests irrevocably. We propose a fair algorithm that uses an interior-point LP solver and dynamically detects unfair resource spending. Our approach do not formulate the fairness requirement as a constrain in the optimization instance, and instead we address the problem from the perspective of algorithm design.
  arXiv  Detail & Related papers  (2021-10-27T17:45:20Z)
• Supercharging Imbalanced Data Learning With Energy-based Contrastive Representation Transfer [72.5190560787569]
  In computer vision, learning from long tailed datasets is a recurring theme, especially for natural image datasets. Our proposal posits a meta-distributional scenario, where the data generating mechanism is invariant across the label-conditional feature distributions. This allows us to leverage a causal data inflation procedure to enlarge the representation of minority classes.
  arXiv  Detail & Related papers  (2020-11-25T00:13:11Z)
• Coordinated Online Learning for Multi-Agent Systems with Coupled Constraints and Perturbed Utility Observations [91.02019381927236]
  We introduce a novel method to steer the agents toward a stable population state, fulfilling the given resource constraints. The proposed method is a decentralized resource pricing method based on the resource loads resulting from the augmentation of the game's Lagrangian.
  arXiv  Detail & Related papers  (2020-10-21T10:11:17Z)
• Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation [49.69139684065241]
  Contextual multi-armed bandit (MAB) achieves cutting-edge performance on a variety of problems. In this paper, we propose a hierarchical adaptive contextual bandit method (HATCH) to conduct the policy learning of contextual bandits with a budget constraint.
  arXiv  Detail & Related papers  (2020-04-02T17:04:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.