Maintaining Perfect Matchings

Abstract:

We investigate the minimum-cost perfect matching problem in metric spaces with two stages. In the first stage, an algorithm is confronted with a set of points from a metric space and ought to find a perfect matching among them. Subsequently, an adversary can announce new points after which the algorithm has to give a perfect matching on the extended set. However, for every arrived point, the algorithm can only do a constant number of reallocations with respect to the old matching. We call an algorithm for this problem (two-stage) robust if the cost of each matching is within a constant factor of those induced by a minimum-cost matching.

For general metric spaces, we can find a matching which is immune to the arrival of k new points, where k must be specified before the construction of the first matching. For the special case where the metric space is the real line together with the Euclidean distance, we present an algorithm that is robust to the arrival of any (unknown) number of points. Our results can be seen as a first step towards solving the online version of the problem.

This is joint work with José Verschae and Jannik Matuschke.

Posted on Aug 6, 2018 in ACGO, Seminars