论文标题
多重MST封面：通过简单的投票规则最佳地取悦所有
Multiagent MST Cover: Pleasing All Optimally via A Simple Voting Rule
论文作者
论文摘要
给定一个连接的图形，我们可以在其边缘上建造路线以连接节点，因此许多代理可能具有不同的视角，应通过分配不同的边缘权重选择边缘。我们的任务是建造最小数量的道路，以便每个代理在内置子图中都有一个生成树，其重量与原始图中的最小跨越树相同。我们首先表明这个问题是NP-HARD，并且不接受$（（1-O（1））\ ln K）$ - 近似多项式时间算法，除非P = NP，否则$ K $是代理的数量。然后，我们以最佳的近似比给出了一种简单的投票算法。此外，我们的算法只需要在边缘上访问代理的排名。最后，我们将结果扩展到了次管的目标函数和Matroid等级约束。
Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than $((1-o(1))\ln k)$-approximation polynomial-time algorithms unless P=NP, where $k$ is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our results to submodular objective functions and Matroid rank constraints.
