16.4 グリーディ彩色アルゴリズム 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム - ryamadaの遺伝学・遺伝統計学メモ点彩色問題の位置 集合があり、その部分集合の作る集合の集合(べき集合)があるときに、与えられた条件のもとでの最適な(ある指標を最小化する)べき集合の組み合わせを求める問題の１つ 最小集合カバー問題と呼ばれる べき集合数は、元の集合の要素数に対して。これの最適組み合わせは容易に大きくなる NP-困難問題のひとつ NP-困難問題は、性能保証された近似アルゴリズムで解くのが現実的 近似アルゴリズム 近似アルゴリズムでは、厳密解に近い解を与えることが知られていることでその近似のよしあしが評価される 近似アルゴリズムの解と厳密解との差が定数内に収まるとき、絶対的近似アルゴリズムであると呼ばれる 近似アルゴリズムの解と厳密解との比が一定定数k内に収まるとき、k-近似アルゴリズムと予備、kを性能比・性能保証・近似比などと呼ぶ 彩色問題は上述の最小集合カバー問題の特殊ケースで絶対的近似アルゴリズムの存在す
