Stochastic Online Metric Matching: Adversarial is no Harder than Stochastic

We study the stochastic online metric matching problem. In this problem, m servers and n requests are located in a metric space, where all servers are available upfront and requests arrive one at a time. In particular, servers are adversarially chosen, and requests are independently drawn from a known distribution. Upon the arrival of a new request, it needs to be immediately and irrevocably matched to a free server, resulting in a cost of their distance. The objective is to minimize the total matching cost. In this paper, we show that the problem can be reduced to a more accessible setting where both servers and requests are drawn from the same distribution by incurring a moderate cost. Combining our reduction with previous techniques, for 0, 1ᵈ with various choices of distributions, we achieve improved competitive ratios and nearly optimal regrets in both balanced and unbalanced markets. In particular, we give O (1) -competitive algorithms for d 3 in both balanced and unbalanced markets with smooth distributions. Our algorithms improve on the O ( (n) ²) competitive ratio of DBLP: conf/icalp/GuptaGPW19 for balanced markets in various regimes, and provide the first positive results for unbalanced markets.