Online Matching with Reusable Network Resources and Decaying Rewards : A Unified Framework

We build a new unified modeling and analysis framework for a broad class of online matching problems. The proposed unified framework encompasses a number of classical online matching problems and accommodates three practical features: reusable resources, network resources and decaying rewards. For the unified framework, we provide a unified performance analysis tool for the greedy policy and greedy-like policies, measured by competitive ratios under adversarial environment. We prove that greedy-like policies can achieve near-optimal performances under the unified framework. We then dig deeper into several representative special classes of online matching problems, which impose additional realistic structural assumptions on top of the unified framework. We prove that slight modifications to greedy-like policies can successfully utilize additional structural information to further enhance policy performances