帕累托最优匹配在动态环境下的调整和相互之间的转换
帕累托最优匹配指的是给一群申请人分配房子，其中每个申请人对他们可以接受的房子有一个优先序列。我们称一个匹配是帕累托最优的即不存在任何其它的匹配使得至少有一个申请人更喜欢新的匹配且没有其他申请人更喜欢原来的匹配。在这里“更喜欢”指的是在某个匹配中获得优先级更高的房子。当在动态环境下申请人和房子可以任意地加入或离开系统时，本文给出一个线性的算法对原来的帕累托匹配作出调整，使匹配仍然能够保持帕累托最优且匹配到尽可能多的申请人。此外本文还证明了任意两个帕累托匹配之间可以通过特殊构造的有向图一步转换到达。
二分图 帕累托匹配 动态环境 转换
王怡慧 Rudolf Fleischer
(复旦大学 计算机科学与工程系，上海 200433)
国内会议
中国系统工程学会模糊数学与模糊系统专业委员会第十四届学术会议
福建武夷山
中文
284-289
2008-10-31（万方平台首次上网日期，不代表论文的发表时间）