A Unified Framework for Online Combinatorial Allocation of Reusable Resources under Endogenous Deterioration
Open Access
- 20 July 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 54 (1) , 10-12
Abstract
This paper studies an online resource allocation problem, where resources are reusable, allocated in combinatorial bundles, and subject to endogenous performance deterioration. Unlike existing models that assume singleton decisions or stationary or exogenous dynamics, we consider a combinatorial decision structure where decisions involve selecting among resource-bundled options, while capturing a self-induced feedback loop in which system performance, like rewards, activation probabilities, and service times, degrade as a function of cumulative resource usage. We propose a unified framework that subsumes a broad class of existing models as special cases, and develop a ranking-like online policy, termed IPRANK, which employs an indicator-perturbation mechanism to induce a randomized ranking over configurations based on their size-penalized rewards. Our analysis is based on a queue-coupling argument and shows that under adversarial arrivals, the greedy policy inevitably suffers a competitive ratio with linear dependence on reward heterogeneity, whereas IPRANK achieves a competitive ratio with only logarithmic dependence, making it far more robust in heterogeneous environments.Keywords
Funding Information
- National Science Foundation (2045641, 2325956, 2512128, and 2533814)
This publication has 15 references indexed in Scilit:
- TAPAS: Thermal- and Power-Aware Scheduling for LLM Inference in Cloud Platforms2025
- Quantifying and Leveraging User Fatigue for Interventions in Recommender Systems2023
- The Online Knapsack Problem with DeparturesProceedings of the ACM on Measurement and Analysis of Computing Systems, 2022
- Online Assortment Optimization with Reusable ResourcesManagement Science, 2022
- Learning To Maximize Welfare with a Reusable ResourceProceedings of the ACM on Measurement and Analysis of Computing Systems, 2022
- Strategic resource decayStrategic Management Journal, 2021
- Dynamic Assortment Optimization for Reusable Products with Random Usage DurationsManagement Science, 2020
- A Large-Scale Study of Flash Memory Failures in the FieldACM SIGMETRICS Performance Evaluation Review, 2015
- Real-Time Optimization of Personalized AssortmentsManagement Science, 2014
- AdWords and generalized online matchingJournal of the ACM, 2007