Jul, 2022

改进无嫉妒匹配算法

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