We consider the problem of assigning agents to programs in the presence of two-sided preferences. Each agent has to be assigned to at most one program and each program can accommodate multiple agents. However unlike the standard setting of school choice, we do not have fixed upper quotas with programs as an input -- instead we abstract it as a cost associated with every program. This setting enables the programs to control the number of agents assigned to them and is also applicable in the two-round setting (Gajulapalli et al., FSTTCS 2020) where largest stable extension is computed. In this setting, our goal is to compute a min-cost stable matching that matches all the agents. We show that the problem is NP-hard even under very severe restrictions on the instance. We complement our negative results by presenting approximation algorithms for general case and a fast exponential algorithm for a special case.


翻译:我们考虑在有双面偏好的情况下向方案指派代理的问题。 每个代理必须被分配到最多一个程序, 每个程序可以容纳多个代理。 但是,与学校选择的标准设置不同, 我们没有固定程序的最高配额作为投入, 我们把它抽象起来作为每个程序的相关成本。 这个设置使程序能够控制分配给它们代理的数量, 并且也适用于计算最大稳定扩展的双轮环境( Gajulapalli 等人, FSTTCS 2020 ) 。 在此设置中, 我们的目标是计算一个与所有代理匹配的低成本稳定匹配。 我们显示, 问题很硬, 即使在非常严格的限制下, 我们通过为普通案例提供近似算法和为特殊案例提供快速指数算法来补充我们的负面结果 。

0
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
专知会员服务
159+阅读 · 2020年1月16日
专知会员服务
115+阅读 · 2019年12月24日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
已删除
将门创投
7+阅读 · 2020年3月13日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
TCN v2 + 3Dconv 运动信息
CreateAMind
4+阅读 · 2019年1月8日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
LibRec 精选:基于LSTM的序列推荐实现(PyTorch)
LibRec智能推荐
50+阅读 · 2018年8月27日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Arxiv
0+阅读 · 2021年3月8日
Arxiv
0+阅读 · 2021年3月8日
Arxiv
3+阅读 · 2018年10月18日
Arxiv
5+阅读 · 2018年5月1日
VIP会员
相关VIP内容
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
专知会员服务
159+阅读 · 2020年1月16日
专知会员服务
115+阅读 · 2019年12月24日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
相关资讯
已删除
将门创投
7+阅读 · 2020年3月13日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
TCN v2 + 3Dconv 运动信息
CreateAMind
4+阅读 · 2019年1月8日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
LibRec 精选:基于LSTM的序列推荐实现(PyTorch)
LibRec智能推荐
50+阅读 · 2018年8月27日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员