エッジとノードの両方に重みがあるグラフ G=(V,E) があります。このグラフを分割して、同じサイズのパーティションを作成したいと考えています。パーティションのサイズの定義は、sum(vi)-sum(ej) です。ここで、vi はそのパーティション内のノードであり、ej はそのパーティション内の 2 つのノード間のエッジです。私の問題では、グラフは非常に密集しています（ほぼ完全です）。そのための近似アルゴリズムはありますか？
これは、ビンのサイズが同じでオブジェクトが重なっているビン パッキングの問題と似ています。ノードの重みはノードのサイズであり、エッジの重みは 2 つのオブジェクトがどれだけオーバーラップできるかを示します。