论文标题
近似多阶段匹配问题
Approximating Multistage Matching Problems
论文作者
论文摘要
在多阶段的完美匹配问题中，我们在同一顶点集中给出了一系列图，并要求找到一系列完美的匹配序列，与图相对应，以便连续匹配尽可能相似。更确切地说，我们旨在最大化交叉点，或最大程度地减少连续匹配之间的工会。我们表明，即使在非常有限的情况下，这些问题也是NP-HARD。我们提出了新的近似算法和当前的方法，以在不同问题变体之间传输结果，而无需失去近似保证。
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.
