グラフ構造をセグメント化するためのマルチカットアルゴリズムに関するいくつかの論文を読んでいます。マルチカット問題の拡張を解決するアルゴリズムを提案するこの作品に特に興味があります。
エッジコストに関しては、次のように述べています。
...ノードの任意のペアについて、これらのノードが個別のコンポーネントにあるすべての分解に対する実数値のコスト (報酬)
けっこうだ。さらに、マルチカット問題の解は、グラフ内のエッジの数に等しい長さの単純なバイナリ ベクトルであり、「1」は、対応するエッジが異なるグラフ コンポーネントに属する 2 つの頂点を分離していることを示します。
すべてのエッジ vw ∈ E ∪ F に対して、v と w が G の異なるコンポーネントにある場合に限り、y(v,w) = 1 になります。
しかし、最適化問題は次のように記述されます。
これは意味がないようです。エッジの重みが異なるコンポーネントのノードを接続するエッジの報酬を表す場合、これは最大化の問題ではないでしょうか? どちらの場合も、すべてのエッジの重みが正の場合、yベクトルがすべてゼロの自明な解が得られるのではないでしょうか? 上記の式の後にはいくつかの制約が続きますが、それらのいずれかがこの結果をどのように妨げているのかわかりませんでした。
さらに、後で貪欲な加法エッジ収縮を使用して初期ソリューションを生成しようとすると、次のように表示されます。
アルゴリズム 1は、単一ノードへの分解から始まります。繰り返しごとに、隣接するコンポーネントのペアが結合され、結合によって目的値が最大に減少します。目的の値を厳密に減少させる結合がない場合、アルゴリズムは終了します。
繰り返しますが、エッジの重みがノードを分離しておくための報酬である場合、任意の 2 つのノードを結合すると報酬が減るのではないでしょうか? そして、エッジの重みがノードを分離しておくためのペナルティであると一瞬仮定したとしても、この方法はすべてのノードを 1 つのコンポーネントにまとめるだけではないでしょうか?
これが機能する唯一の方法は、エッジの重みが正と負の値のバランスの取れた組み合わせである場合ですが、この制約は文献のどこにも言及されていないため、何かが欠けていると確信しています.