• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>ACM transactions on economics and computation >A Fine-grained View on Stable Many-to-one Matching Problems with Lower and Upper Quotas
【24h】

A Fine-grained View on Stable Many-to-one Matching Problems with Lower and Upper Quotas

机译：具有下限和上限的稳定多对一匹配问题的细粒度视图

获取原文
       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the NP-hard Hospital Residents problem with lower and upper quotas (HR-QUL), the goal is to find a stable matching of residents to hospitals where the number of residents matched to a hospital is either between its lower and upper quota or zero. We analyze this problem from a parameterized complexity perspective using several natural parameters such as the number of hospitals and the number of residents. Moreover, answering an open question of Biro et al. TCS 2010, we present an involved polynomial-time algorithm that finds a stable matching (if it exists) on instances with maximum lower quota two. Alongside HR-QUL, we also consider two closely related models of independent interest, namely, the special case of HR-QUL where each hospital has only a lower quota but no upper quota and the variation of HR-QUL where hospitals do not have preferences over residents, which is also known as the House Allocation problem with lower and upper quotas. Last, we investigate the parameterized complexity of these three NP-hard problems when preferences may contain ties.
机译：在赋权医院居民的问题上下配额(HR-QUL),这样做的目的是找到一个稳定的匹配的居民到医院居民的数量匹配到哪里医院上下之间配额或零。参数化的复杂性角度使用一些自然的数量等参数医院和居民的数量。回答开放式问题的比罗et al . (TCS2010),我们提供了一个多项式时间算法,找到一个稳定的匹配(如果它存在)实例以最大降低配额两个。模型的独立利益密切相关,也就是说,HR-QUL每个的特殊情况医院只有较低的配额,但没有上配额和HR-QUL的变化,医院没有对居民的偏好,是哪一个也称为分配问题上下配额。参数化这三个np难的复杂性问题的偏好可能包含关系。

著录项

相似文献

  • 外文文献
  • 中文文献
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号