Speaker
Description
In the dynamic matching problem, customers arrive according to a Poisson process and must be matched to available servers within a network of queues. These servers independently replenish and renege from the market. Previous literature on the dynamic matching problem often concentrates on static policies—where the matching decisions are not adapted to dynamic information on queue lengths. In this work, we formulate tighter, yet efficient linear programming relaxations that optimize an adaptive matching process, where the queue lengths inform the matching decisions in real-time.
We develop two applications of this linear programming (LP) framework that provide new formal approximation algorithms for the dynamic matching problem. First, we devise a bi-criteria polynomial-time approximation scheme for a cost-minimization version of dynamic matching on Euclidian networks of fixed dimensions. The goal is to find a matching policy that approaches any feasible target for matching the cost rate and throughput rate arbitrarily closely. The approximation scheme combines our new LP framework with an instance decomposition that allocates the cost-throughput rate targets across localized subproblems. Second, we devise a (1−1/𝑒)-balanced contention resolution scheme for our linear program. This result matches the best-known approximation for the reward maximization problem, but the new matching policy is guided by queue length information and is simpler to analyze than in previous literature.
