# Approximating Multistage Matching Problems

arXiv: https://arxiv.org/abs/2002.06887 · HTML: https://mlsanity.com/paper/2002.06887/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2020.

## Built on by (most cited first, 1 of 1)

- [Accelerating Matroid Optimization through Fast Imprecise Oracles](https://mlsanity.com/paper/2402.02774/) (2024)

## Abstract (arXiv)

In multistage perfect matching problems we are given a sequence of graphs on the same vertex set and asked to find a sequence of perfect matchings, corresponding to the sequence of graphs, such that consecutive matchings are as similar as possible. More precisely, we aim to maximize the intersections, or minimize the unions between consecutive matchings. We show that these problems are NP-hard even in very restricted scenarios. We propose new approximation algorithms and present methods to transfer results between different problem variants without loosing approximation guarantees.