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

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

• •連立構造生成（CSG）問題に対するさまざまなアルゴリズムパラダイムを比較。
• •特定のモデルの下で、スパース緩和が多項式時間でほぼ最適な解を達成できることを証明。
• •DPおよびMILPと比較して、スパース緩和に有利な確率的随時分離を実証。
• •複雑な問題に対するスパース緩和の計算効率を強調。