The Parameterized Complexity of Connected Fair Division
The Parameterized Complexity of Connected Fair Division
复制标题
连接公平划分的参数化复杂性
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
S. Ordyniak
中科院分区：
文献类型：
--
作者：
Argyrios Deligkas;E. Eiben;R. Ganian;Thekla Hamm;S. Ordyniak
我们研究了连接的公平部门问题（CFD），该问题通过要求分配给每个代理的项目在提供的项目图G中形成一个连接的子图，从而概括了将资源分配给代理商的基本问题。综合的复杂性理论理解CFD基于几种新算法和下限，同时考虑了几种公平的公平概念：相称性，嫉妒性， EF1和EFX。特别是，我们表明，要实现障碍，需要以有意义的方式限制代理和项目图。我们设计（XP） - 算法的问题，该问题由（1）G的Clique宽度加上代理的数量和（2）g的g width g加上代理类型的数量，以及相应的下限。最后，我们表明，要实现固定参数障碍性，不仅需要使用更严格的参数化，还需要将最大项目估值作为附加参数包含。
We study the Connected Fair Division problem (CFD), which generalizes the fundamental problem of fairly allocating resources to agents by requiring that the items allocated to each agent form a connected subgraph in a provided item graph G. We expand on previous results by providing a comprehensive complexity-theoretic understanding of CFD based on several new algorithms and lower bounds while taking into account several well-established notions of fairness: proportionality, envy-freeness, EF1 and EFX. In particular, we show that to achieve tractability, one needs to restrict both the agents and the item graph in a meaningful way. We design (XP)-algorithms for the problem parameterized by (1) clique-width of G plus the number of agents and (2) treewidth of G plus the number of agent types, along with corresponding lower bounds. Finally, we show that to achieve fixed-parameter tractability, one needs to not only use a more restrictive parameterization of G, but also include the maximum item valuation as an additional parameter.