BriefGPT - AI 论文速递
·
无嫉妒图切割的复杂性
原文中文，约400字，阅读约需1分钟。
📝
内容提要
这篇研究论文研究了公平地分配异质可分资源给具有不同偏好的个体的问题。问题是NP完全的，但当个体数量是常数时，可以设计多项式时间算法。
🎯
关键要点
-
研究公平地分配异质可分资源给不同偏好的个体的问题。
-
资源对应于一张连接图的边缘，每个个体必须被分配一块连通的图形。
-
关注的公平概念是经典的无嫉妒性。
-
该问题是 NP 完全的。
-
分析了相对于个体数量和图中边缘数量的复杂性。
-
即使对于只有两名个体的实例，该问题仍然是 NP 困难的。
-
当个体数量是常数时，给出了该问题复杂性的两分法特征。
-
设计了一个多项式时间算法，当图形具有常数数量的边时。
