图公平定向的参数化复杂度
Research Paper#Graph Theory, Parameterized Complexity, Fair Division🔬 Research|分析: 2026年1月3日 06:13•
发布: 2025年12月31日 18:30
•1分で読める
•ArXiv分析
本文研究了在图中寻找公平定向的计算复杂度，这个问题与公平分配场景相关。它侧重于EF（无嫉妒）定向，这比EFX定向研究得更少。本文的重要性在于其参数化复杂度分析，确定了简单图和多重图的可处理情况、硬度结果和参数化。它还提供了关于EF和EFX定向之间关系的见解，回答了一个悬而未决的问题并改进了现有工作。在定向设置中对慈善事业的研究进一步扩展了本文的贡献。