用于联盟结构生成的稀疏松弛

本文研究了用于联盟结构生成（CSG）问题的有效算法，CSG是博弈论中的一个经典问题。它比较了动态规划（DP）、MILP分支定界和稀疏松弛方法。关键发现是，在特定的随机模型下，稀疏松弛可以在多项式时间内找到接近最优的联盟结构，在随时性能方面优于DP和MILP算法。这很重要，因为它为解决复杂问题提供了一种计算效率高的方法。