不同合成稳定室友实例的映射
论文介绍了一种针对稳定婚姻问题的 n 元约束,其能够保持稳定且禁止重婚,在处理 n 个男人和 n 个女人的稳定婚姻实例时,只需要一个该约束,并且强制执行弧一致性的复杂性是 O(n^2),其计算研究表明该 n-ary constraint 比文献中的编码更快且更节省空间,同时提出了一个新的约束问题,即性别平等的稳定婚姻问题。
Aug, 2013
本文通过使用ASP编码,提出了一种能自由适应特定应用需求且具有高效率的算法来解决稳定婚姻问题,并且尝试基于用户需求选择最优匹配方案。此编码为首个能在考虑到指定不接受伴侣和允许多种匹配程度下找到完全符合性等、最小后悔和最大基数的SMP实例的精确实现, 该方法将会在TPLP上发表。
Dec, 2015
本研究探讨了稳定匹配问题中鲁棒性的概念,定义了(a,b)-超级匹配,并将最鲁棒的稳定匹配定义为(1,b)-超级匹配,我们用多项式时间检查给定的稳定匹配是否为(1,b)-超级匹配,然后设计了约束编程模型、局部搜索方法和遗传算法以找到最鲁棒的稳定匹配,实验证明局部搜索优于其他方法。
May, 2017
针对频繁出现在匹配多个对象(例如图像或形状)问题中的部分排列,我们研究置换同步问题。使用基于非负因式分解的算法解决了置换同步问题,采用一种新的旋转方案进行初始化,以方便欧几里得投影,得到了二进制解。与现有的方法相比,我们的方法保证产生一致的结果,并在实验中证明了其有效性。
Mar, 2018
介绍了 SRTI-ASP 这一 Answer Set Programming 的形式化框架,并使用其解决了 Stable Roommates problem 变体问题。
Aug, 2020
本文研究了一个变化的稳定婚姻问题,其中每个男人和每个女人都将他们的偏好表达为可能不完整且包含并列关系的偏好列表,考虑了三种优化变体,并通过比较Answer Set Programming,约束编程和整数线性编程等方法来解决这些问题。对于最大基数,我们还比较了这些方法与局部搜索方法。本文还对Answer Set Programming与命题可满足性进行了实证比较。
Aug, 2021
在一项研究中,我们引入了个体偏好稳定性(IP稳定性),作为一种受稳定性和公平性约束启发的自然聚类目标。我们证明了对于一般度量,总存在一个O(1)-IP稳定的聚类算法,并且还介绍了IP稳定性在平均距离以及簇内和簇间最大最小距离情况下的推广。
Sep, 2023
通过将其转化为“稳定固件”问题的实例,我们提出了一个多项式时间算法,可在具有不精确的稳定配对问题实例中(通过将医院的容量调整不超过1)找到近似可行的稳定配对;我们还提出了一个多项式时间算法来解决具有“双重市场”的不精确、不完整实例。
Nov, 2023
本研究针对稳定婚姻问题及医院/居民问题中的不完全列表和决胜情况,提出了一种基于决胜的局部搜索算法(TBLS)。该算法通过调节偏好顺序,在最大化匹配规模的同时,推出了一种关注公平性的变体TBLS-E,显著提升了性别平等性并保持了较高的匹配规模。与现有算法相比,TBLS和TBLS-E在计算速度和匹配效果上均表现出色。
Sep, 2024