2026-08-17T20:01:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10643 2024-03-06T10:46:21Z ddc:004 open_access

Stochastic Online Metric Matching Gupta, Anupam Guruganesh, Guru Peng, Binghui Wajc, David stochastic online online matching metric matching We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive online, each drawn independently from a known probability distribution over the points. Each request has to be matched to a free server, with cost equal to the distance. The goal is to minimize the expected total cost of the matching. Such stochastic arrival models have been widely studied for the maximization variants of the online matching problem; however, the only known result for the minimization problem is a tight O(log n)-competitiveness for the random-order arrival model. This is in contrast with the adversarial model, where an optimal competitive ratio of O(log n) has long been conjectured and remains a tantalizing open question. In this paper, we show that the i.i.d model admits substantially better algorithms: our main result is an O((log log log n)^2)-competitive algorithm in this model, implying a strict separation between the i.i.d model and the adversarial and random order models. Along the way we give a 9-competitive algorithm for the line and tree metrics - the first O(1)-competitive algorithm for any non-trivial arrival model for these much-studied metrics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anupam Gupta and Guru Guruganesh and Binghui Peng and David Wajc 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.67 urn:nbn:de:0030-drops-106430 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.67 eng https://creativecommons.org/licenses/by/3.0/legalcode