论文标题
与图表生成联盟结构的分支和结合算法
A Branch and Bound Algorithm for Coalition Structure Generation over Graphs
论文作者
论文摘要
我们使用估值函数为联盟结构生成基于列的分支和界限算法，该算法被证明是NP完整的。对于给定的图G =（V; e）和估值函数W：2^V-> r，问题是找到V的最有价值的联盟结构（或分区）。我们考虑两种情况：首先，当联盟的价值是其边缘的重量之和可以是正或负面的重量时，当联盟的价值均可为正面和内在的情况下，并考虑到互相不同意。对于这两种估值，我们都给出了实验结果，这些结果首先涵盖了40多个代理商。 对于另一个估值函数（协调），我们仅在附录中给出理论考虑。
We give a column generation based branch and bound algorithm for coalition structure generation over graphs problem using valuation functions for which this problem is proven to be NP-complete. For a given graph G = (V;E) and a valuation function w : 2^V -> R, the problem is to find the most valuable coalition structure (or partition) of V. We consider two cases: first when the value of a coalition is the sum of the weights of its edges which can be positive or negative, second when the value of a coalition takes account of both inter- and intra-coalitional disagreements and agreements, respectively. For both valuations we give experimental results which cover for the first time sets of more than forty agents. For another valuation function (coordination) we give only the theoretical considerations in the appendix.
