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.APPROX/RANDOM.2020.37
URN: urn:nbn:de:0030-drops-126401
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12640/
Go to the corresponding LIPIcs Volume Portal

Megow, Nicole ; Nölke, Lukas

Online Minimum Cost Matching with Recourse on the Line

pdf-format:
LIPIcs-APPROX37.pdf (0.5 MB)

Abstract

In online minimum cost matching on the line, n requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all on the real line. The goal is to minimize the sum of distances from the requests to their respective servers. Despite all research efforts, it remains an intriguing open question whether there exists an O(1)-competitive algorithm. The best known online algorithm by Raghvendra [S. Raghvendra, 2018] achieves a competitive factor of Θ(log n). This result matches a lower bound of Ω(log n) [A. Antoniadis et al., 2018] that holds for a quite large class of online algorithms, including all deterministic algorithms in the literature.
In this work, we approach the problem in a recourse model where we allow to revoke online decisions to some extent, i.e., we allow to reassign previously matched edges. We show an O(1)-competitive algorithm for online matching on the line with amortized recourse of O(log n). This is the first non-trivial result for min-cost bipartite matching with recourse. For so-called alternating instances, with no more than one request between two servers, we obtain a near-optimal result. We give a (1+ε)-competitive algorithm that reassigns any request at most O(ε^{-1.001}) times. This special case is interesting as the aforementioned quite general lower bound Ω(log n) holds for such instances.

BibTeX - Entry

@InProceedings{megow_et_al:LIPIcs:2020:12640,
  author =	{Nicole Megow and Lukas N{\"o}lke},
  title =	{{Online Minimum Cost Matching with Recourse on the Line}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Jaros{\l}aw Byrka and Raghu Meka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12640},
  URN =		{urn:nbn:de:0030-drops-126401},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.37},
  annote =	{Keywords: min-cost matching in bipartite graphs, recourse, competitive analysis, online}
}

Keywords: min-cost matching in bipartite graphs, recourse, competitive analysis, online
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Issue Date: 2020
Date of publication: 11.08.2020

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