IJCAIDec, 2023

无嫉妒图切割的复杂性

TL;DR这篇研究论文主要研究公平地分配一组异质可分资源给具有不同偏好的个体的问题,关注的是资源对应于一张连接图的边缘,每个个体必须被分配一块连通的图形,所考虑的公平概念是经典的无嫉妒性。该问题是 NP 完全的,我们分析了该问题相对于两个自然复杂度度量的复杂性:个体数量和图中边缘的数量。虽然即使对于只有两名个体的实例问题仍然是 NP 困难的,但我们根据图的结构性质给出了当个体数量是常数时该问题复杂性的两分法特征。对于后一种情况,我们设计了一个多项式时间算法,当图形具有常数数量的边时。