確率的目的関数のPTIMEまたはNP-硬度


前の投稿
をリンクすることから始めます。ここでは私が下で説明する確率的設定について一般的な質問をしました。制限されたケースの私の「証明」は間違いがあり、硬度を表示する方が簡単になるはずの設定がはるかに簡単であることが判明しました。代わりに元の質問を修正する必要があるかどうか教えてください。

$ n $ verticesと$ m $ edgesを持つグラフ$ G =(V、E)$を考えてみましょう。各頂点$ v_i
$は、確率$ p_i $と確率$ 1-p_i $の値$ 0 $を持つ正の値$ a_i $を取ることができます。 $ G
$はすべての頂点が次数$ 2 $(および$ m = n $)を持つサイクルになるように制限します。

課題は、各エッジにウェイト$ w_e $を割り当てて、 ここで、$ Pr [X_i + X_j geq w_e]
$は、その総和が次のようになる確率を表します。$ Pr {X_i + X_j geq w_e} $は、頂点$ i $と$ j
$がとる値のうち$ w_e $より大きい。付加的な制約は、重み$ w_e
$が副次的になる必要があることである。すなわち、任意の2つのエッジ$ e ‘$と$ e “‘ $は”エッジ “$ e $ $ ‘$と$
e’ ‘$は$ e $を作る頂点を含み、それは$ w_e leq w_ {e’} + w_ {e ”} $を保持します。

$ p_i = 1
$の確定的なバージョンが自明であることを確認してください。硬度やPTIMEアルゴリズムの可能な方向に関する提案は非常に役立ちます!

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です