标题： 基于优先级的稳定匹配问题局部搜索算法 显示英文标题

标题： A Tie-breaking based Local Search Algorithm for Stable Matching Problems

摘要： 稳定婚姻问题中的不完整列表和绑定（SMTI）以及带有绑定的医院/居民问题（HRT）在匹配理论中具有重要意义，并有广泛的实际应用。 在本文中，我们引入了一种基于绑定打破的局部搜索（TBLS）算法，旨在为SMTI和HRT问题实现最大规模的弱稳定匹配。 TBLS首先任意解决所有绑定，并通过根据偏好等级和当前稳定匹配调整绑定内的相对顺序来迭代地改进绑定打破策略。 此外，我们引入了TBLS-E，这是针对SMTI问题的一个注重公平性的TBLS变体。 该变体保持最大化匹配规模的目标，同时通过两个简单的修改增强公平性。 与另外十种近似和局部搜索算法相比，TBLS实现了最高的匹配规模，而TBLS-E表现出最低的性别平等成本。 显著的是，TBLS-E保持了与TBLS相当的匹配规模。 我们的两种算法在解决大规模实例时都比其他局部搜索算法具有更快的计算速度。 此外，我们的可扩展性分析表明，随着问题规模的增加，两种算法都能保持高效的性能。 显示英文摘要

摘要： The stable marriage problem with incomplete lists and ties (SMTI) and the hospitals/residents problem with ties (HRT) are important in matching theory with broad practical applications. In this paper, we introduce a tie-breaking based local search (TBLS) algorithm designed to achieve a weakly stable matching of maximum size for both the SMTI and HRT problems. TBLS begins by arbitrarily resolving all ties and iteratively refines the tie-breaking strategy by adjusting the relative order within ties based on preference ranks and the current stable matching. Additionally, we introduce TBLS-E, an equity-focused variant of TBLS, specifically designed for the SMTI problem. This variant maintains the objective of maximizing matching size, while enhancing equity through two simple modifications. In comparison with ten other approximation and local search algorithms, TBLS achieves the highest matching size, while TBLS-E exhibits the lowest sex equality cost. Significantly, TBLS-E preserves a matching size comparable to that of TBLS. Both our algorithms demonstrate faster computational speed than other local search algorithms in solving large-scale instances. Moreover, our scalability analysis shows that both algorithms maintain efficient performance as problem size increases.