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]^d\) 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 \ge 3\) in both balanced and unbalanced markets with smooth distributions. Our algorithms improve on the \(O((\log \log \log n)^2)\) competitive ratio of Gupta et al. (ICALP’19) for balanced markets in various regimes, and provide the first positive results for unbalanced markets.