バイナリ変数のセットに対する関数の加重和を最大化する複雑さ

a_1 in {0,1 } $のバイナリ変数$ a_1、…、a_n $があるとします。今度は、$ m
$を定義し、それらのサブセットに作用します:$$ j in {1、…、m }:f_j = x_1 land x_2
land … land x_k $$ $$ {x_1、…、x_k } subset
{a_1、…、a_n } $$

各変数$ a_i $にそれに割り当てられたコスト$ c_i $があり、すべての関数$ f_j $にそれに関連する利益$ p_j
$があるとします。両方の変数は、非負の$ forall i、j:p_j、c_i ge 0 $です。

問題は、すべての可能な$ a_i $ sのセットに対して、利益からコストを差し引いたものをどのように最大化するかです。
$$(1) max_ {a_1、…、a_n} left { sum_j ^ m p_j f_j – sum_i ^
n c_i a_i right } $$

もう1つの関連する問題は、一定の$ C $の制約付きコストで利益を最大化することです。 $$(2) max _ {
sum_i c_i a_i le C} left { sum_j ^ n p_j f_j right }
$$のようになります。

今私が持っている質問はここにここにあります:

  1. $(1)$を厳密に多項式で解くことができるか、または 擬似多項式の方法?
  2. $(2)$を解決できるか 擬似多項式時間?

擬似多項式とは、$ | c_i | $と$ | p_j |
$の境界を仮定することで、多項式時間アルゴリズムを実現できますか?

$(2)$疑似多項式解法$(1)$には、さまざまな値の$ C
$を反復することによって擬似多項式解が得られることは明らかです。したがって、ある意味では、$(2)$はより困難な問題です。さらに、$
f_j = a_j
$を設定すると、ナップザックは$(2)$の特殊なケースとみなすことができます。したがって、厳密に多項式にすることはできません。しかし、私はこれらの2つの問題の複雑さについてもっと詳しく話すことはできません。

ベストアンサー

(1) has a polynomial solution. Consider a graph with source $s$,
sink $t$, vertices $U$ corresponding to the variables and vertices
$V$ corresponding to the functions. If $f_j = x_1 land ldots
land x_k$ then add edges $f_j to x_i$ for each $i in
{1,ldots,k}$ with capacities equal to $C$ for $C > sum p_j$.
Add edges $x_i to t$ with capacities $c_i$ and edges $s to f_j$
with capacities $p_j$. Consider minimum cut between $s$ and $t$ in
this graph (it could be easily found with almost any maximal-flow
algrorithm). Let $U_s subseteq U$ and $V_s subseteq V$ be the
sets of vertices in the component of $s$. Then the value of the
minimum cut is $$sumlimits_{i in U_s} c_i + sumlimits_{j
notin V_s} f_j = underbrace{sumlimits_{jin V}
f_j}_{text{constant}} – underbrace{left(-sumlimits_{i in U_s}
c_i + sumlimits_{j in V_s} f_jright)}_{text{objective
function}}$$ Thus if this value is minimised, the objective
function is maximised. On the other hand $U_s$ and $V_s$ for
minimum cut have the property that if $x_1 land ldots land x_k =
f_j in V_s$ then $x_1, ldots, x_k in U_s$ since otherwise the
value of the cut is $ge C$ which is not optimal. Thus setting
$x=1$ for $x in U_s$ and $x=0$ for $x notin U_s$ gives an
optimal solution for (1).

任意の$ p_j $を持つ場合は、多項式に限定された$ | p_j | $であっても$ mathbf {NP} text
{ – } mathrm {complete} $です。

If you allow $p_j$ to be negative, you can
reduce $mathrm{max}text{-}mathrm{SAT}$ to this problem. For each
variable $x_i$ of $mathrm{max}text{-}mathrm{SAT}$ add two
variables $x_i$ and $lnot x_i$ to your input. For each of these
pair add the condition $x_i land lnot x_i$ with the cost $-C$ for
a large enough constant $C$. For all clauses of
$mathrm{max}text{-}mathrm{SAT}$ input add the corresponding
conjunction with all literals reversed: $x lor lnot y lor z$
becomes $lnot x land y land lnot z$ (here $lnot x$ and $lnot
z$ are variables in the new problem). $lnot x land y land lnot
z iff lnot (x lor lnot y lor z)$ therefore each unsatisfied
conjunctions correspond to satisfied clauses. Thus you can set the
cost $p$ for each conjunction as $-1$. For $c_i = 0$ for all $i in
{1,ldots, n}$, $m -max left{sumlimits_j f_j p_j –
sumlimits_i a_i c_iright}$ (where $m$ is the number of clauses
in the $mathrm{max}text{-}mathrm{SAT}$ instance) is the maximum
number of clauses that could be satisfied in the instance of
$mathrm{max}text{-}mathrm{SAT}$ or a value greater than or equal
to $C – n$ if the instance is unsatisfiable. Thus $C = 3n$ is “big
enough”. I.e. for negative $p_j$ there is no polynomial solution
even with bounded $|p_j|$ and $|c_j|$ unless $mathbf{P} =
mathbf{NP}$.

返信を残す

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