Aug, 2013

稳定婚姻问题的n-元约束

HTML
PDF
TL;DR论文介绍了一种针对稳定婚姻问题的 n 元约束，其能够保持稳定且禁止重婚，在处理 n 个男人和 n 个女人的稳定婚姻实例时，只需要一个该约束，并且强制执行弧一致性的复杂性是 O(n^2)，其计算研究表明该 n-ary constraint 比文献中的编码更快且更节省空间，同时提出了一个新的约束问题，即性别平等的稳定婚姻问题。
发现论文，激发创造
  • 使用答案集编程解决稳定匹配问题

    本文通过使用ASP编码，提出了一种能自由适应特定应用需求且具有高效率的算法来解决稳定婚姻问题，并且尝试基于用户需求选择最优匹配方案。此编码为首个能在考虑到指定不接受伴侣和允许多种匹配程度下找到完全符合性等、最小后悔和最大基数的SMP实例的精确实现， 该方法将会在TPLP上发表。

    Dec, 2015

  • 稳定婚姻中的鲁棒解决方案

    本研究探讨了稳定匹配问题中鲁棒性的概念，定义了（a，b）-超级匹配，并将最鲁棒的稳定匹配定义为（1，b）-超级匹配，我们用多项式时间检查给定的稳定匹配是否为（1，b）-超级匹配，然后设计了约束编程模型、局部搜索方法和遗传算法以找到最鲁棒的稳定匹配，实验证明局部搜索优于其他方法。

    May, 2017

  • 使用答案集编程的稳定室友问题通用框架

    介绍了 SRTI-ASP 这一 Answer Set Programming 的形式化框架，并使用其解决了 Stable Roommates problem 变体问题。

    Aug, 2020

  • 基于知识的稳定室友问题：一个真实世界的应用

    本研究介绍了一种基于知识的干预方法用于解决稳定室友问题（SRTI），并探讨了它在大学宿舍中分配学生室友的现实应用。

    Aug, 2021

  • 带有约束和不完整偏好的稳定婚姻问题：ASP，SAT，ILP，CP 和本地搜索方法的实证比较

    本文研究了一个变化的稳定婚姻问题，其中每个男人和每个女人都将他们的偏好表达为可能不完整且包含并列关系的偏好列表，考虑了三种优化变体，并通过比较Answer Set Programming，约束编程和整数线性编程等方法来解决这些问题。对于最大基数，我们还比较了这些方法与局部搜索方法。本文还对Answer Set Programming与命题可满足性进行了实证比较。

    Aug, 2021

  • 双半联盟稳定匹配问题：基于批准的申请者-雇主关系匹配

    本文提出 Dichotomous Affiliate Stable Matching (DASM) 问题，通过权衡代理人和其关联方的接受或拒绝并基于加权估值函数来解决匹配市场偏好问题，通过人类研究和算法验证，证明该方法的高效性。

    Feb, 2022

  • 改进无嫉妒匹配算法

    本文研究了当每个代理人被分配一个单品时的无嫉妒匹配问题，并提出了一种称为变革者无嫉妒匹配的改进方案，我们研究从一个初始的无嫉妒匹配到达变革者无嫉妒匹配的最短序列，当每个代理人接受的物品不超过3个或者每个物品被至多两个代理人接受时，提供了多项式时间算法。同时，本文讨论了无法近似和固定参数（不）可计算性。

    Jul, 2022

  • 不同合成稳定室友实例的映射

    本文针对稳定室友问题，引入可计算假度量来评估这些问题相似度的工具，并使用它来创建稳定室友实例的图表，展示其为非聚合可视化工具的实用性。此外，还创建了稳定婚姻实例的图表用于其他匹配问题下的实验。

    Aug, 2022

  • 夫妻可追溯性：医院/住户问题的新算法和难度结果

    通过将其转化为“稳定固件”问题的实例，我们提出了一个多项式时间算法，可在具有不精确的稳定配对问题实例中（通过将医院的容量调整不超过1）找到近似可行的稳定配对；我们还提出了一个多项式时间算法来解决具有“双重市场”的不精确、不完整实例。

    Nov, 2023

  • 基于决胜的局部搜索算法解决稳定匹配问题

    本研究针对稳定婚姻问题及医院/居民问题中的不完全列表和决胜情况，提出了一种基于决胜的局部搜索算法（TBLS）。该算法通过调节偏好顺序，在最大化匹配规模的同时，推出了一种关注公平性的变体TBLS-E，显著提升了性别平等性并保持了较高的匹配规模。与现有算法相比，TBLS和TBLS-E在计算速度和匹配效果上均表现出色。

    Sep, 2024