在冲突制约下公平分配不可分割的货物 (Fair allocation of indivisible goods under conflict constraints)

from arxiv, A preliminary version containing some of the results presented here appeared in the proceedings of IWOCA 2020. Version 3 contains an appendix with a remark about biconvex bipartite graphs

We consider the fair allocation of indivisible items to several agents and add a graph theoretical perspective to this classical problem. Thereby we introduce an incompatibility relation between pairs of items described in terms of a conflict graph. Every subset of items assigned to one agent has to form an independent set in this graph. Thus, the allocation of items to the agents corresponds to a partial coloring of the conflict graph. Every agent has its own profit valuation for every item. Aiming at a fair allocation, our goal is the maximization of the lowest total profit of items allocated to any one of the agents. The resulting optimization problem contains, as special cases, both {\sc Partition} and {\sc Independent Set}. In our contribution we derive complexity and algorithmic results depending on the properties of the given graph. We can show that the problem is strongly NP-hard for bipartite graphs and their line graphs, and solvable in pseudo-polynomial time for the classes of chordal graphs, cocomparability graphs, biconvex bipartite graphs, and graphs of bounded treewidth. Each of the pseudo-polynomial algorithms can also be turned into a fully polynomial approximation scheme (FPTAS).

翻译：我们考虑将不可分割的项目公平分配给多个代理商, 并给这个古典问题添加一个图表理论角度。因此, 我们引入了冲突图中描述的对等项目之间的不兼容关系。分配给一个代理商的每组项目都必须在本图中形成独立的设置。因此, 分配给代理商的项目分配与冲突图的部分颜色相对应。每个代理商都有其自身的利润价值。为了公平分配, 我们的目标是最大限度地增加分配给任何一个代理商的物品的最低总利润。由此产生的优化问题包含特殊案例, 包括作为特例的 ~sc 分割 } 和 ~sc 独立设置。在我们的贡献中, 我们根据给定图的特性来得出复杂性和算法结果。我们可以表明, 问题对于两边图及其线图来说, 问题非常严重, 而对于圆形图、相容图、相容图、双convex 双部分图以及绑定的树际图。每一个多面面图也成为了完全的模型。