Stochastic Online Metric Matching: Adversarial is no Harder than Stochastic
- Mingwei Yang, Stanford University
- Time: 2024-12-10 10:00
- Host: Turing Class Research Committee
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
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 Gupta et al. (ICALP'19) for balanced markets in various regimes, and provide the first positive results for unbalanced markets.
Biography
Mingwei Yang is a second-year Ph.D. student in Operational Research at Stanford University. Prior to joining Stanford, he received his bachelor's degree at Turing Class, Peking University. His research interests broadly lie in theoretical computer science with recent focus on counting and sampling algorithms, online matching algorithms, and fair division.