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 (α, β)-robust if the solutions constructed in both stages are α-approximate with respect to min-cost perfect matchings, and if the number of edges deleted from the first stage matching is at most βk. Hence, α measures the quality of the algorithm and β its robustness. In this setting we aim to balance both measures by deriving algorithms for constant α and β. 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 (19, 2)-robust algorithm that constructs a solution with a recursive structure that carefully balances cost and redundancy.
To the best of our knowledge, the only work which considers recourse for online min-cost matching is the recent work REF where the authors consider a two-stage version of the uni-chromatic problem (where there is no distinction between servers and clients): In the first stage, a perfect matching between 2n given nodes must be selected; in the second stage 2k new nodes are introduced.
Maintaining Perfect Matchings at Low Cost
ArXiv
ArXiv
Computer Science Mathematics