Stochastic Online Metric Matching: Adversarial is no Harder than Stochastic
<|reference_start|>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 \geq 3$ in both balanced and unbalanced markets with smooth distributions. Our algorithms improve on the $O((\log \log \log n)^2)$ competitive ratio of \cite{DBLP:conf/icalp/GuptaGPW19} for balanced markets in various regimes, and provide the first positive results for unbalanced markets.<|reference_end|>
@article{saberi2024stochastic,
    title={Stochastic Online Metric Matching: Adversarial is no Harder than
  Stochastic},
    author={Amin Saberi, Mingwei Yang, Sophie H. Yu},
    journal={arXiv preprint arXiv:2407.14785},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.14785},
    primaryClass={cs.DS}
}