最大3色アルゴリズム

Question

私はグラフG = (V,E)を与えられています。この問題では、目標は、品質機能に

Q（C）=の数を最大化可能3色でグラフの頂点の色を見つけることですその端点が異なる色をしている辺。

確率的な3/2近似を与えて、各自然数kと固定されたd>= 1に対して最大でd^-kの確率でアルゴリズムが失敗（悪化近似を意味する）することを示します。

ここでは、次のアルゴリズムを与えました。各頂点をランダムに色付けします。つまり、エッジが異なる色のエッジを持つと予想される確率は2/3で3/2近似になります。

しかし、返り値が最大でもd^-kで失敗することを示す方法はわかりません。

ありがとうございました！

Answer 1

ここで数量化を解くのではなく、次の確定的に実装可能な欲張りアルゴリズムが正しいことを証明するために、条件付き期待値の方法を使用することができます。

無色の頂点が存在しますが、隣接する色の中で最も色が薄い色の1つに色付けします。

考えられるのは、グラフの残りの部分をランダムに色付けすると仮定して、他の選択肢に関係なく、無彩色の端点を持つ各辺が期待値の2/3の価値があるという考えです。最も多様な選択肢を使用することにより、無作為化された価値を失ったものと少なくとも同じくらい決定的な価値を得ることができます。