解决动态奖励下可复用服务器的在线匹配问题，提升算法鲁棒性。
Online Bipartite Matching with Reusable Capacity under Non-Stationary Rewards
- 基于局部奖励约束设计时间感知的平衡算法
- 理论竞争比达 $\ln(δD)$，优于传统方法
- 适合高波动场景下的资源调度应用
研究在非平稳奖励下具有可复用容量的在线二分图匹配问题。任务依次到达，揭示兼容服务器、奖励率和处理时长，必须不可撤销地接受或拒绝。已接受任务仅在处理期间占用服务器容量单位，可能挤占未来未知任务。现有保证通常依赖全局奖励范围，当奖励长期漂移时该范围可能无限扩大。本文提出局部有界奖励条件：在同一相关时间窗内可竞争同一服务器的任务，其奖励率差异不超过因子 $δ$。在此条件下，设计两种类似 BALANCE 的算法，引入时间感知的机会成本损失。TS-BAL 最大化可行复用调度下的累积阻塞损失，实现竞争比 $2\ln(δD)+\mathcal O(\ln\ln(δ\vee D))$；GR-BAL 采用该损失的贪心松弛，达到 $\ln(δD)+\mathcal O(\ln\ln(δ\vee D))$，与 $\ln(δD)$ 的最优下界首项一致。数值实验表明算法在显著全局奖励漂移下表现稳健，且有限容量性能优越。
原文摘要 · Abstract (English)
We study online bipartite matching with reusable server capacity and non-stationary rewards. Jobs arrive sequentially, reveal compatible servers, reward rates, and processing durations, and must be accepted or rejected irrevocably. An accepted job occupies one unit of server capacity only during its processing interval, so an assignment may displace an unknown sequence of future jobs. Existing guarantees are typically calibrated by a global reward range, which can become arbitrarily large when rewards drift over a long horizon. We instead impose a locally bounded reward condition: reward rates of jobs that can compete for the same server within a relevant time window differ by at most a factor $δ$. Under this condition, we develop two BALANCE-type algorithms with time-aware opportunity-cost losses. TS-BAL maximizes cumulative blocking losses over feasible reuse schedules and achieves a competitive ratio of $2\ln(δD)+\mathcal O(\ln\ln(δ\vee D))$. GR-BAL uses a greedy relaxation of this loss and achieves $\ln(δD)+\mathcal O(\ln\ln(δ\vee D))$, matching a lower bound of $\ln(δD)$ in the leading term. Numerical experiments demonstrate robust performance under substantial global reward drift and favorable finite-capacity performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。