ユークリッド施設のNP硬度/ k-中央変異体

Facility Location Problem(FLP)は次のように定義されています。

入力:クライアントのCと潜在的施設の$ F $、F $内のすべての$ i に対してコスト$ f_i $を、C $内のすべての$
i に対する接続コストc_ {ij}を設定する。
タスク:F ‘}内の$ sum_ {i F_i + sum_ {j in C} min_ {i in
F’} c_ {ij} $のようなサブセット$ F ‘$ of $ F $を選択します。最小です。

FLPは、例えば、セットカバー(クライアントは要素であり、設備はセットである)からの単純な削減など、メトリック距離であってもNP困難である。

ユークリッド(または幾何学的)FLPクライアントとファシリティでは、$ mathbb {R} ^ 2 $と$ c_ {ij}
$はユークリッド距離です。調査の記事「NPハード幾何学の近似スキーム
最適化の問題:Aroraによるアンケートでは、この亜種もNP困難であると主張しているようです(21ページ「以下に列挙するすべての問題は、別段の記載がない限りNP困難です。論文はこの結果を含んでも参照していません。

Question 1: Is the euclidean FLP known to be
NP-hard?

コストを開放することなく修正された問題であるが、開かれた施設の数に制限があることは、$ k $
-median問題に非常に近いと思われる。

入力:$ mathbb {R} ^ 2 $の点の$ C $を設定します。
タスク:$ sum_ {j in_ { f}} $ min_ {i} $が最小になるように$ F $ of $ k $
pointsを選択します。

この問題と、$ F $が$ C $のサブセットでなければならない変種は、NP-hard(制限なし:

いくつかの一般的な幾何学的位置問題の複雑さについては、幾何学的位置問題の最悪ケースと確率的解析)。

Question 2: Is the modified problem without
opening costs but with only $k$ allowed facilities known to be
NP-hard?

Update: I found an answer to the second
question (this problem contains the median variant with restriction
as the special case where $F = C$), but am still interested in the
first.

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

返信を残す

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