We give a simple approximation algorithm for a common generalization of many previously studied extensions of the stable matching problem with ties. These generalizations include the existence of critical vertices in the graph, amongst whom we must match as much as possible, free edges, that cannot be blocking edges and $\Delta$-stabilities, which mean that for an edge to block, the improvement should be large enough on one or both sides. We also introduce other notions to generalize these even further, which allows our framework to capture many existing and future applications. We show that our edge duplicating technique allows us to treat these different types of generalizations simultaneously, while also making the algorithm, the proofs and the analysis much simpler and shorter then in previous approaches. In particular, we answer an open question by Askalidis et al. (2013) about the existence of a $\frac{3}{2}$-approximation algorithm for the Max-SMTI problem with free edges. This demonstrates well that this technique can grasp the underlying essence of these problems quite well and have the potential to be able to solve countless future applications as well.

翻译：我们提供了一种简单的近似算法，适用于许多先前研究过的稳定匹配问题的常见推广。这些推广包括图中存在关键顶点，必须尽可能地匹配他们之间的线，不能被阻塞的自由边，以及$\Delta$-稳定性，这意味着为了阻塞，改进在一方或双方应该足够大。我们还介绍了其他概念，以进一步推广这些问题，从而使我们的框架能够捕捉到许多现有和未来的应用程序。我们展示了我们的边重复技术如何使我们能够同时处理这些不同类型的推广，同时使算法、证明和分析比以前的方法更简单、更短。特别地，我们回答了Askalidis等人（2013）关于具有自由边的Max-SMTI问题存在$\frac{3}{2}$-近似算法的开放问题。这很好地说明了这种技术可以很好地把握这些问题的基本本质，并有能力解决无数未来的应用程序。