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.
翻译:在多阶段完美匹配问题中,在同一个顶点设置上,我们被给定了一个图表序列,要求我们找到一个与图表序列相对应的完美匹配序列,以便相继匹配尽可能相似。更准确地说,我们的目标是尽量扩大交叉点,或者尽量减少连续匹配之间的交汇点。我们显示,这些问题即使在非常有限的情景下也是难以解决的。我们提出了新的近似算法和目前在不同问题变量之间转移结果的方法,而不会失去近似保证。