COMICS · CATALOGUE 102
Unique Games予想と最適近似限界
The Unique Games Conjecture and optimal approximation thresholds
Unique Gamesのギャップ問題、3SATからの帰着、近似の難しさとMax-Cutの近似限界を紹介します。 カタログ内の全原稿・全結果を網羅するものではありません。
このサイトの解説には、誤りや不正確な説明が含まれる可能性があります。重要な主張・証明は原論文でご確認ください。
COMICS · CATALOGUE 102
The Unique Games Conjecture and optimal approximation thresholds
Unique Gamesのギャップ問題、3SATからの帰着、近似の難しさとMax-Cutの近似限界を紹介します。 カタログ内の全原稿・全結果を網羅するものではありません。