提出高效算法在多项式时间内生成接近最优的联盟结构。
Near-Optimal Coalition Structures in Polynomial Time
- 采用稀疏松弛方法，通过贪心或l1型策略快速求解
- 在随机稀疏联盟模型下，解的质量接近最优且时间多项式
- 适合需要快速近似解的场景，如大规模群体协作
我们研究经典的联盟结构生成（CSG）问题，对比动态规划（DP）、MILP分支定界以及基于贪心或l1型方法的稀疏松弛三种算法范式的即时行为。在联盟价值的简单随机‘稀疏协同’模型下，证明稀疏松弛可在高概率下以多项式时间恢复接近最优的联盟结构。相比之下，广泛的DP和MILP算法需指数时间才能达到类似解的质量。这确立了稀疏松弛在概率意义上的严格优势，尽管精确方法最终仍可达到最优。
原文摘要 · Abstract (English)
We study the classical coalition structure generation (CSG) problem and compare the anytime behavior of three algorithmic paradigms: dynamic programming (DP), MILP branch-and-bound, and sparse relaxations based on greedy or $l_1$-type methods. Under a simple random "sparse synergy" model for coalition values, we prove that sparse relaxations recover coalition structures whose welfare is arbitrarily close to optimal in polynomial time with high probability. In contrast, broad classes of DP and MILP algorithms require exponential time before attaining comparable solution quality. This establishes a rigorous probabilistic anytime separation in favor of sparse relaxations, even though exact methods remain ultimately optimal.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。