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.82
URN: urn:nbn:de:0030-drops-106582
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10658/
Go to the corresponding LIPIcs Volume Portal

Matuschke, Jannik ; Schmidt-Kraepelin, Ulrike ; Verschae, José

Maintaining Perfect Matchings at Low Cost

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

Abstract

The min-cost matching problem suffers from being very sensitive to small changes of the input. Even in a simple setting, e.g., when the costs come from the metric on the line, adding two nodes to the input might change the optimal solution completely. On the other hand, one expects that small changes in the input should incur only small changes on the constructed solutions, measured as the number of modified edges. We introduce a two-stage model where we study the trade-off between quality and robustness of solutions. In the first stage we are given a set of nodes in a metric space and we must compute a perfect matching. In the second stage 2k new nodes appear and we must adapt the solution to a perfect matching for the new instance.
We say that an algorithm is (alpha,beta)-robust if the solutions constructed in both stages are alpha-approximate with respect to min-cost perfect matchings, and if the number of edges deleted from the first stage matching is at most beta k. Hence, alpha measures the quality of the algorithm and beta its robustness. In this setting we aim to balance both measures by deriving algorithms for constant alpha and beta. We show that there exists an algorithm that is (3,1)-robust for any metric if one knows the number 2k of arriving nodes in advance. For the case that k is unknown the situation is significantly more involved. We study this setting under the metric on the line and devise a (10,2)-robust algorithm that constructs a solution with a recursive structure that carefully balances cost and redundancy.

BibTeX - Entry

@InProceedings{matuschke_et_al:LIPIcs:2019:10658,
  author =	{Jannik Matuschke and Ulrike Schmidt-Kraepelin and Jos{\'e} Verschae},
  title =	{{Maintaining Perfect Matchings at Low Cost}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{82:1--82: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/10658},
  URN =		{urn:nbn:de:0030-drops-106582},
  doi =		{10.4230/LIPIcs.ICALP.2019.82},
  annote =	{Keywords: matchings, robust optimization, approximation algorithms}
}

Keywords: matchings, robust optimization, approximation algorithms
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