• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >POPULAR MATCHINGS WITH TIES AND MATROID CONSTRAINTS
【24h】

POPULAR MATCHINGS WITH TIES AND MATROID CONSTRAINTS

机译：带有领带和母体约束的热门比赛

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Assume that we are given a set of applicants and a set of posts such that each applicant has a preference list over the posts. A matching M between the applicants and the posts is said to be popular if there is no other matching N such that the number of applicants that prefer N to M is larger than the number of applicants that prefer M to N. Then, the goal of the popular matching problem is to decide whether there is a popular matching, and find a popular matching if one exists. Abraham, Irving, Kavitha, and Mehlhorn proved that this problem can be solved in polynomial time even if the preference lists contain ties. In this paper, we consider the popular matching problem with matroid constraints. In this problem, for each post, we are given a matroid on the set of applicants. A set of applicants assigned to each post must be an independent set of its matroid. Kamiyama proved that if there is not a tie in the preference lists, then this problem can be solved in polynomial time. In this paper, we prove that even if there are ties in the preference lists, this problem can be solved in polynomial time.
机译：假设给了我们一组申请人和一组职位，以使每个申请人都有一个职位偏好列表。如果没有其他匹配的N，从而使从N到M的申请人数大于从M到N的申请人数，则认为申请人和职位之间的匹配M很受欢迎。流行匹配的问题是确定是否存在流行匹配，如果存在则找到流行匹配。亚伯拉罕（Abraham），欧文（Irving），卡维萨（Kavitha）和梅尔霍恩（Mehlhorn）证明，即使偏好列表包含联系，该问题也可以在多项式时间内解决。在本文中，我们考虑了具有拟阵约束的流行匹配问题。在这个问题上，对于每个职位，我们都会在申请者集上设置一个拟阵。分配给每个职位的一组申请人必须是独立的拟阵。 Kamiyama证明，如果偏好列表中没有平局，则可以在多项式时间内解决此问题。在本文中，我们证明即使偏好列表中存在联系，该问题也可以在多项式时间内解决。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号