每日 Arxiv

本页面整理了世界各地发表的人工智能相关论文。
本页面使用 Google Gemini 汇总而成，并以非盈利为基础运营。
论文版权归作者及相关机构所有，分享时请注明出处。

公平定位杂务的多项式时间算法

Created by
  • Haebom

作者

Kevin Hsu、Valerie King

公平任务分配图方向搜索

大纲

本文探讨了在任务图中寻找公平方向的问题，其中每个顶点代表一个代理，每条边代表一项任务。如果某任务对应的边与代理不相邻，则该任务对代理的边际效用为0。周等人（IJCAI，2024）分析了在商品和任务混合图中确定EFX方向的复杂度，并推测在仅包含任务的图中确定EFX方向是NP完全的。本文通过提供一个多项式时间算法来解决这一猜想，该算法用于在仅包含任务的图中（即使存在自循环）寻找EF1和EFX方向。值得注意的是，该结果显示了商品和任务情况之间的显著差异。此外，本文证明了多重图中EF1和EFX方向问题的NP完全性。

Takeaways, Limitations

•
我们提出了一种多项式时间算法来查找仅包含任务的图的 EF1 和 EFX 方向。
•
证明确定仅包含产品的图的 EFX 方向的问题与确定仅包含任务的图的 EFX 方向的问题之间的差异。
•
多重图的 EF1 和 EFX 定向问题的 NP 完全性证明。
•
论文中没有提到具体的算法实现或者性能分析。
•
没有讨论该算法对现实世界任务分配场景的适用性。
👍
Made with Slashpage