License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.67
URN: urn:nbn:de:0030-drops-106430
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10643/
Go to the corresponding LIPIcs Volume Portal

Gupta, Anupam ; Guruganesh, Guru ; Peng, Binghui ; Wajc, David

Stochastic Online Metric Matching

pdf-format:
LIPIcs-ICALP-2019-67.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{gupta_et_al:LIPIcs:2019:10643,
  author =	{Anupam Gupta and Guru Guruganesh and Binghui Peng and David Wajc},
  title =	{{Stochastic Online Metric Matching}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10643},
  URN =		{urn:nbn:de:0030-drops-106430},
  doi =		{10.4230/LIPIcs.ICALP.2019.67},
  annote =	{Keywords: stochastic, online, online matching, metric matching}
}

Keywords: stochastic, online, online matching, metric matching
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI