1 Search Results for "Schmidt-Kraepelin, Ulrike"


Document
Track A: Algorithms, Complexity and Games
Maintaining Perfect Matchings at Low Cost

Authors: Jannik Matuschke, Ulrike Schmidt-Kraepelin, and José Verschae

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


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.

Cite as

Jannik Matuschke, Ulrike Schmidt-Kraepelin, and José Verschae. Maintaining Perfect Matchings at Low Cost. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 82:1-82:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{matuschke_et_al:LIPIcs.ICALP.2019.82,
  author =	{Matuschke, Jannik and Schmidt-Kraepelin, Ulrike and Verschae, Jos\'{e}},
  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 =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.82},
  URN =		{urn:nbn:de:0030-drops-106582},
  doi =		{10.4230/LIPIcs.ICALP.2019.82},
  annote =	{Keywords: matchings, robust optimization, approximation algorithms}
}
  • Refine by Author
  • 1 Matuschke, Jannik
  • 1 Schmidt-Kraepelin, Ulrike
  • 1 Verschae, José

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms

  • Refine by Keyword
  • 1 approximation algorithms
  • 1 matchings
  • 1 robust optimization

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail