偏好序阈值约束下的三边单向非循环稳定匹配

杨洋,赵晓冬

系统科学与数学 ›› 2020, Vol. 40 ›› Issue (8) : 1420-1431.

PDF(557 KB)
PDF(557 KB)
系统科学与数学 ›› 2020, Vol. 40 ›› Issue (8) : 1420-1431. DOI: 10.12341/jssms13932
论文

偏好序阈值约束下的三边单向非循环稳定匹配

    杨洋1,2,赵晓冬1
作者信息 +

A Three-sided Unidirectional Acyclic Stable Matching with Thresholds of Preference Order

    YANG Yang 1,2 ,ZHAO Xiaodong1
Author information +
文章历史 +

摘要

文章针对单向非循环偏好下的三边匹配问题, 提出了一种基于偏好序阈值 约束条件下的匹配算法. 首先, 基于单向非循环偏好结构, 给出了三边单向非循环匹 配及其稳定性的有关定义, 并建立了一对一情形下满足系统稳定性需求的数学模型; 然后, 通过设置偏好序阈值对模型进行约束限制, 提出了偏好序阈值约束下的两阶段逐 边优选算法, 并分别对该算法的时间复杂度及输出匹配的稳定性进行了计算和证明. 最 后, 通过一个算例验证文章所提算法的可行性和有效性.

Abstract

Aiming at three-sided matching problems with unidirectional acyclic preferences, a matching algorithm based on thresholds of preference order is proposed in this paper. First, based on the unidirectional acyclic structure, the definition of three-sided unidirectional acyclic matching and its stability are given, and the mathematical model to meet the stability requirements of the system is established. Second, thresholds of preference order are set to constrain the model, an edge-by-edge optimization algorithm in two stages with thresholds of preference order is proposed, and the time complexity of the algorithm and the stability of the output scheme are calculated and proved respectively. Finally, an example is given to verify the feasibility and effectiveness of the proposed algorithm.

关键词

三边匹配 / 非循环偏好 / 稳定性 / 偏好序 / 时间复杂度.

引用本文

导出引用
杨洋 , 赵晓冬. 偏好序阈值约束下的三边单向非循环稳定匹配. 系统科学与数学, 2020, 40(8): 1420-1431. https://doi.org/10.12341/jssms13932
YANG Yang , ZHAO Xiaodong. A Three-sided Unidirectional Acyclic Stable Matching with Thresholds of Preference Order. Journal of Systems Science and Mathematical Sciences, 2020, 40(8): 1420-1431 https://doi.org/10.12341/jssms13932
PDF(557 KB)

Accesses

Citation

Detail

段落导航
相关文章

/