Nov, 2023

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

HTML
PDF
TL;DR通过将其转化为“稳定固件”问题的实例，我们提出了一个多项式时间算法，可在具有不精确的稳定配对问题实例中（通过将医院的容量调整不超过1）找到近似可行的稳定配对；我们还提出了一个多项式时间算法来解决具有“双重市场”的不精确、不完整实例。
发现论文，激发创造
  • 稳定婚姻问题的n-元约束

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

    Aug, 2013

  • 大肾交换图的小表示

    本文研究肾脏交换问题，提出如果肾脏交换兼容性图可以用固定数量的患者和捐献者属性来编码，则可以在多项式时间内清除肾脏交换问题。

    May, 2016

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

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

    May, 2017

  • 通过严格和弱偏好的交换实现对象可到达性

    这篇论文在研究房屋市场的资源分配问题，使用社交网络模型，探讨代理人之间的交易，提出了多项解决方案，其中包括了一种可在多项偏好下求解的多项式时间算法以及在路径网络中求解最优分配问题的复杂性分析。

    Sep, 2019

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

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

    Aug, 2020

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

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

    Aug, 2021

  • 蒙特卡罗树搜索在医学住院匹配中的自适应容量扩展

    探究两个医院之间如何更好地分配实习医生的问题，并提出了一种基于上限置信树和延迟批准方法的容量扩张算法，该算法能够通过较小的计算预算来获得几乎最优的解决方案。

    Feb, 2022

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

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

    Aug, 2022

  • 多轮匹配实现资源共享

    针对多轮匹配问题，我们在普遍应用实践中探究了解决资源与代理人之间的配对问题的方法，并研究了不同类型的收益函数的解决策略，同时针对不同的场景，我们提出了整数线性规划和基于局部搜索的启发式算法。

    Nov, 2022

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

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

    Sep, 2024