連立構造生成におけるスパース緩和

本論文は、ゲーム理論における古典的な問題である連立構造生成（CSG）問題に対する効率的なアルゴリズムを研究しています。動的計画法（DP）、MILP分枝限定法、およびスパース緩和法を比較しています。主な発見は、特定のランダムモデルの下で、スパース緩和法が多項式時間でほぼ最適な連立構造を見つけることができ、随時性能の点でDPおよびMILPアルゴリズムを上回るということです。これは、複雑な問題に対する計算効率の高いアプローチを提供するという点で重要です。