2

各ポイントと特定のセットAの間の最小距離を最大化する、特定のカーディナリティkのセットSを見つけたいと思います。この最大最小問題の解を見つける簡単なアルゴリズムはありますか?

Given a universe X ⊆ R^d and A ⊆ X,
find the argmax_{S⊆X, |S|=k} min_{s⊆S, s'≠s ⊆ S∪A} distance(s,s')

ありがとう ！

4

3 に答える 3

3

入力として X と A を持つ与えられた k の場合、総当たり攻撃は明らかに P にあります (C(|X|,k) は |X| の多項式であるため)。

k も入力の場合、 'distance' に依存する可能性があります。

「距離」が任意の場合、問題はグラフ内の固定サイズのクリークを見つけることと同等です (これは NP 完全です)。

NP-硬度:

グラフ (G,E) と整数 k であるクリーク問題のインスタンスを取り上げます。このグラフに、他のすべての頂点に接続された頂点 'a' を追加します。(G',E') を修正したグラフとします。

(G',E') k+1 は、クリーク問題の最初のインスタンスと同等のインスタンスです。

G' から R^d へのマップ Phi を作成し (とにかく G' を N にマップできます ...)、距離 (Phi(c),Phi(d')) = 1 if (c, d) ⊆ E'、それ以外の場合は 0。

X = Phi(G'), A = Phi({a}), k+1 は、問題のインスタンスを示します。

構造により、s ≠ Phi(a) <=> distance(s,Phi(A)) = 1 = max distance(.,.)、つまり min_{s⊆S, s'≠s ⊆ S∪A であることがわかります。 } distance(s,s') = min_{s⊆S, s'≠s ⊆ S} 距離(s,s') if |S| = k >= 2

問題のこのインスタンス (X,A,k+1) を解きます。これにより、min( distance(s,s') |s,s'⊆ S, s≠s' となる基数 k+1 のセット S が得られます。 ) が最大です。

s,s'⊆ S, s≠s', distance(s,s') = 0 があるかどうかを確認します (これは |S| = k として k^2 で実行できます) :

  • その場合、forall s,s' distance(s,s') = 1 となるカーディナリティ k+1 のセットはありません。つまり、k+1 クリークである G' の部分グラフはありません。
  • そうでない場合は、S を G' にマップし直します。「距離」の定義により、Phi^-1 (S) の任意の頂点間にエッジがあります。これは k+1 クリークです。

これは、クリーク問題 (NP 困難として知られている) と同等の問題を多項式簡約で解決します。

NP-容易さ:

X、A、k を問題のインスタンスとします。

X min_{s⊆S, s'≠s ⊆ S∪A} の任意のサブセット S に対して、距離(s,s') は {距離(x,y), x,y ⊆ X} でのみ値を取ることができます。多項式基数-。

この距離を最大化するセットを見つけるために、可能なすべての距離をテストして正しいセットを降順にテストします。

距離 d をテストするには、まず X を A の距離 >= d にある点のみを含む X' に減らします{点自体}。

次に、グラフ (X',E) ¤ ((s,s') ⊆ E iff distance(s,s') >= d) を作成します。

このグラフを k-clique でテストします (これは NP が簡単です)。頂点 S が min_{s⊆S, s'≠s ⊆ S∪A} distance(s,s' ) >= d

「距離」がユークリッドであるか、それが P である可能性がある何か面白い特性を持っている場合、私にはわかりませんが、私があなただったとしても、あまり期待しません.

¤ ここで X (したがって X') は有限であると仮定しました

于 2012-06-12T21:13:21.370 に答える
1

検索の上位 2 つの結果はsphere packing np complete、2d での最適なパッキングとカバーが np 完全であることを証明する 1981 年の論文への参照を示しました。研究図書館にアクセスできないので、論文を読むことができません。しかし、あなたの問題はそのように言い換えることができると思います。その場合、NP完全問題があるという証拠があります。

于 2012-06-12T17:36:58.763 に答える
1

これはおそらく NP 困難です。以前の選択から最も離れたポイントを貪欲に選択することは、2 近似です。Arora と Mitchell によるユークリッド TSP のスキームに基づく低 d の複雑な近似スキームが存在する可能性があります。d = 10 の場合は忘れてください。

于 2012-06-12T16:02:06.863 に答える