On the Stability of Minimum-Weight Perfect Matching on the Line
2026-07-17 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study how to keep a good matching between points on a line when points can be added or removed over time. They focus on algorithms that only change a limited number of connections (edges) after each update, aiming to keep the matching nearly optimal. They provide an algorithm that changes about the square root of the number of points each time and guarantees a matching at most twice as long as the best possible. They also prove that if an algorithm changes fewer edges than that, its performance can become very bad. These results apply even when points only get added, and also to a related bipartite matching problem.
minimum-weight perfect matchingdynamic algorithmsonline algorithmsbounded recourseapproximation ratiostabilityEuclidean spacebipartite matchinginsertion-only updatesfully dynamic updates
Authors
Mark de Berg, Ulrike Schmidt-Kraepelin, Andree-Ovidiu Stef
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 $\mathbb{R}^1$. First, we present an $O(\sqrt{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.