分割マトローラ制約下での単調スーパーモジュラ関数の最小化

最小化問題の既知の近似アルゴリズムはありますか?
パーティションmatroidの制約のもとで、単調増加(非増加)の超モード関数?

ベストアンサー

グラフ$ G =(V、E)$を考えてみましょう。集合関数$ f $ over $ V $を定義する。ここで、$
f(A)$は両端点を$ A $に持つ辺の数である。 $ f $はスーパーモジュラと単調である。 $ G $にサイズ$ k
$の独立した集合があるとします。次に、制約$ | S |の下にある$ f(S)$の最小値は、 = k $(均一なマトロイド制約)は$
0 $になります。 $ G $にサイズ$ k $の独立したセットがない場合、minは少なくとも$ 1
$になります。したがって問題は近づきません。

返信を残す

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