DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.27

On the Stability of Minimum-Weight Perfect Matching on the Line

Authors: Mark de Berg, Ulrike Schmidt-Kraepelin, and Andree-Ovidiu Ștef

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

Computing a minimum-weight perfect matching for a point set P in Euclidean space is a classic geometric optimization problem. We consider the problem in a dynamic setting, where pairs of points may be added to or removed from the set P. Our focus is on maintaining an approximately optimal solution without making too many changes to the solution. More precisely, we are interested in k-stable algorithms, which change at most k edges in the matching after each update to the set P. In other words, we consider an online setting (with insertions and deletions) with bounded recourse. We study trade-offs between the stability of the algorithm and the approximation ratio of the maintained solution for point sets in ℝ¹. First, we present an O(√n)-stable algorithm that maintains a 2-approximation, which we show to be optimal among all algorithms with sublinear stability. Second, we prove that any o(log n)-stable algorithm has unbounded approximation ratio. Our lower bounds hold even in the insertion-only case, while our algorithm works in the fully dynamic case. Moreover, our lower bounds also hold for the bipartite variant of the problem.

Cite as

Mark de Berg, Ulrike Schmidt-Kraepelin, and Andree-Ovidiu Ștef. On the Stability of Minimum-Weight Perfect Matching on the Line. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ESA.2026.27,
  author =	{de Berg, Mark and Schmidt-Kraepelin, Ulrike and Ștef, Andree-Ovidiu},
  title =	{{On the Stability of Minimum-Weight Perfect Matching on the Line}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.27},
  URN =		{urn:nbn:de:0030-drops-271632},
  doi =		{10.4230/LIPIcs.ESA.2026.27},
  annote =	{Keywords: Euclidean matching, stable approximation algorithms, dynamic algorithms, online algorithms, bounded recourse}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2019.82

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.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}
}

Search Results

Documents authored by Schmidt-Kraepelin, Ulrike

On the Stability of Minimum-Weight Perfect Matching on the Line

Abstract

Cite as

Maintaining Perfect Matchings at Low Cost

Abstract

Cite as

Thanks for your feedback!

Could not send message