{-1、+1}行列の行を最大にする0-1ベクトルを求めるNP硬度

以下の離散最適化問題を考えてみましょう。$ { – 1、+1 } $のエントリを持つ$ m $次元のベクトル$
{v_1、 dots、v_n } $の集合があれば、 $ x $の正のドット積を持つベクトル$ v_i $の数を最大にする$
{0,1 } $のエントリを持つ2次元ベクトル$ x $を返します。

For example, for the collection of vectors given by the rows of
the matrix $$ begin{bmatrix} -1 & -1 & -1 & -1 \ +1 & +1 & -1 &
-1 \ +1 & -1 & +1 & -1 \ -1 & +1 & +1 & -1 \ -1 & -1 & -1 & -1
end{bmatrix} $$ the optimal choice of $x$ is $[1, 1, 1, 0]^T$,
which has positive dot products with the middle three rows.

この問題はNP困難であることが知られていますか?もしそうなら、多項式時間近似アルゴリズムは利用可能ですか?

(mathoverflowからのクロス投稿:
https://mathoverflow.net/questions/288136/np-hardness-of-finding-0-1-vector-to-maximize-rows-of-1-1-matrix

ベストアンサー

この問題はNP困難です。実際、すべてのドット積が正であるようなxの選択肢が存在するかどうかを決定することさえ、NP完全である。私はセットカバーからの削減によってこれを以下に示します。

削減

数$ k $からなるセットカバーインスタンスが与えられ、$ S_1、S_2、 ldots、S_m subseteq
{1,2、 ldots、n } $が設定されているとします。対応する問題は、$ {1,2、 ldots、n }
$の部分集合$ C $が$ | C |で存在するかどうかです。 = k $であり、各$ S_i $には$ C
$の少なくとも1つの要素が含まれています(または$ S_i cap C $は$ i $ごとに空ではない)。

この入力を使用して、問題のインスタンス、つまり同じ長さの$ { – 1、1 }
$を超えるベクトルの集合を構築します。これらのベクトルの長さは$ n + k + 1 $になり、その中に$ m + k + 2
$があります。特に、以下で定義されるベクトル$ a $、$ b_1、b_2、 ldots、b_ {k + 1} $、$
c_1、c_2、 ldots、c_m $を持ちます。

$ 1(n)$を長さ$ n $のベクトルで表し、その値はすべて$ 1 $ sです。 $ i $ th $値が$ 1
$で、他の値が$ -1 $である長さ$ n $のベクトルを$ e_i(n)$とする。 $ s_j $は、長さ$ n
$のベクトルであり、$ i $番目の値は、S_j $と$ -1 $の場合は$ i $です。

その後、

  • $ a = [〜1(k + 1)〜;〜-1(n)〜] $
  • $ 1 le j le k + 1 $には$ b_j = [〜e_j(k + 1)〜;〜1(n)〜] $となります。

  • $ c_j = [〜-e_1(k + 1)〜;〜s_j〜] $ for $ 1 le j le n $

正しさ

長さ$ k + 1 $の2つの部分ベクトル$ x ‘$と$ x “$として表現される$ 0 $ sと$ 1 $
sの任意のベクトルを$ x = [〜x’〜; x ”〜] $とする$ n $。

Suppose that the dot product of $x$ with vectors $a$, $b_1$,
$ldots$, and $b_{k+1}$ is positive. その後、 consider the two vectors
$a$ and $b_j$ (for some $j$). These two vectors are almost exactly
negatives of each other. In particular, they both have $1$ as the
$j$th component but are otherwise negatives of each other (this is
easy to verify). その後、 if $x$ is a vector of $0$s and $1$s with a
$0$ in the $j$th component, the dot product of $x$ with $a$ is the
negative of the dot product of $x$ with $b_j$. In this case, these
two dot products cannot both be positive. Therefore, $x$ must have
a $1$ in the $j$th component.

The above logic can be applied for every $j$ with ($1 le j le
k+1$). From this, we can conclude that if $x$ has a positive dot
product with vectors $a$, $b_1$, $ldots$, and $b_{k+1}$, その後、 $x’
= 1(k+1)$.

Furthermore, we know that $x cdot a > 0$, and $$x cdot a =
[~x’~;~x”~] cdot [~1(k+1)~;~-1(n)~]= [~1(k+1)~;~x”~] cdot
[~1(k+1)~;~-1(n)~] = 1(k+1) cdot 1(k+1) + x” cdot -1(n) = k+1 –
|x”|_1$$ where $|x”|_1$ is the number of $1$s in $x”$, so
$k+1-|x”|_1 > 0$ and $|x”|_1 < k+1$.

Similarly, $x cdot b_1 > 0$, and $$x cdot b_1 =
[~x’~;~x”~] cdot [~e_1(k+1)~;~1(n)~]= [~1(k+1)~;~x”~] cdot
[~e_1(k+1)~;~1(n)~] = 1(k+1) cdot e_1(k+1) + x” cdot 1(n) =
-(k-1) + |x”|_1,$$ so $-(k-1)+|x”|_1 > 0$ and $|x”|_1 >
k-1$.

Together the above implies that $|x”|_1 = k$. To summarize, we
have shown that if $x$ has a positive dot product with vectors $a$,
$b_1$, $ldots$, and $b_{k+1}$, その後、 $x’ = 1(k+1)$ and $|x”|_1 =
k$. In fact, it is easy to verify that the reverse is also true. In
other words, $x = [~x’~;~x”~]$ has a positive dot product with
vectors $a$, $b_1$, $ldots$, and $b_{k+1}$ if and only if $x’ =
1(k+1)$ and $|x”|_1 = k$.

これからは、上記の形のベクトル$ x $だけを考えてみましょう。サイズ$ k $の可能なベクトル$ x ”と部分集合$
{1、 ldots、n } $との間には1対1の対応があることに注意してください。特に$ x ” $を入れることができます$ X
subseteq {1、 ldots、n } $との対応| X | X | = k $のような$(x ”)_i = 1
$ iff $ i のようなk $。

この対応では、$ x $がベクトル$ c_1 $、$ ldots $、および$ c_n
$で正のドット積を持つための必要十分条件を考えることができます。

For any $j$, we can expand $x cdot c_j$ as $$x cdot c_j =
[~1(k+1)~;~x”~] cdot [~-e_1(k+1)~;~s_j~] = 1(k+1) cdot -e_1(k+1)
+ x” cdot s_j = (k-1) + x” cdot s_j.$$ Notice that the value of
$x” cdot s_j$ is exactly a sum of $k$ components of $s_j$: in
particular, $x” cdot s_j = sum_{i in X}(s_j)_i$. If these $k$
components are all $-1$s, その後、 this sum is $-k$, and so $x cdot
c_j = (k-1) + x” cdot s_j = (k-1) + -k = -1 < 0$. If these $k$
components include at least one $1$, その後、 this sum is at least
$-1times(k-1) + 1times 1 = -(k-2)$ in which case $x cdot c_j =
(k-1) + x” cdot s_j ge (k-1) + -(k-2) = 1 > 0$. Thus, we see
that $x cdot c_j ge 0$ for a specific $j$ if and only if $X$
includes at least one $i$ such that $(s_j)_i = 1$.

$(s_j)_i = 1 $はS_j $の$ i の場合にのみ忘れないでください。従って、特定の$ j $のための$ x
cdot c_j ge 0 $は、S_j $の$ i のように$ X $が少なくとも一つの$ i $を含む場合にのみ、あるいは$
X cap S_j $は空ではありません。

その後、 $x cdot c_j ge 0$ for every $j$ if and only if for every
$j$, $X cap S_j$ is not empty. Notice that the latter condition is
exactly equivalent to the condition that $X$ is a solution to the
input set cover instance.

In summary, we see that $x$ is a vector of $0$s and $1$s with
positive dot product with all the vectors produced by the 削減 if and
only if $x = [~1(k+1)~;~x”~]$ with $|x”|_1 = k$ and $x”$
corresponds to a set $X subseteq {1, ldots, n}$ with $|X| = k$
such that $X$ is a solution to the input instance of set cover. In
other words, a solution to the set cover instance exists if and
only if a solution to the instance produced by the 削減 exists.

返信を残す

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