Optimal Control of General Dynamic Matching Systems
Mohammadreza Nazari, Alexander Stolyar · arXiv (Cornell University) · 2016
We consider a matching system with random arrivals of items of multiple types. The items wait in queues, one queue per each type, until they are matched with other items; after a matching is complete, the associated items leave the system. There exists a finite number of possible matchings, each producing a certain amount of reward. In this paper, we propose an optimal matching policy in the sense that it asymptotically maximizes the long-term average matching reward, while keeping the queues stable. This algorithm is constructed by applying an extended version of the greedy primal-dual (GPD) algorithm to a virtual system (with possibly negative queues). The proposed algorithm is real-time, it does not require any knowledge of the arrival rates; at any time it uses a simple rule, based on the current state of virtual queues.