diff options
Diffstat (limited to 'paper/sections/model.tex')
| -rw-r--r-- | paper/sections/model.tex | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/paper/sections/model.tex b/paper/sections/model.tex index 5d64acf..ee24eec 100644 --- a/paper/sections/model.tex +++ b/paper/sections/model.tex @@ -77,6 +77,6 @@ the transition matrix of the Markov chain. This observation led to the development of fast algorithms for influence maximization under the voter model~\cite{even-dar}.\newline -\noindent \textbf{\textsc{NP}-Hardness.} In contrast to standard influence maximization, adaptive seeding is already \textsc{NP}-Hard even for the simplest influence functions such as $f(S) = |S|$ and when all probabilities are one. We discuss this in Appendix~\ref{sec:alg-proofs}. +\noindent \textbf{\textsc{NP}-Hardness.} In contrast to standard influence maximization, adaptive seeding is already \textsc{NP}-Hard even for the simplest influence functions such as $f(S) = |S|$ and when all probabilities are one. We discuss this in the full version of the paper~\cite{full}. %In the case when $f(S)=|S|$ and all probabilities equal one, the decision problem is whether given a budget $k$ and target value $\ell$ there exists a subset of $X$ of size $k-t$ which yields a solution with expected value of $\ell$ using $t$ nodes in $\mathcal{N}(X)$. It is easy to see that this problem is \textsc{NP}-hard by reduction from \textsc{Set-Cover}. %This is equivalent to deciding whether there are $k-t$ nodes in $X$ that have $t$ neighbors in $\mathcal{N}(X)$. To see this is \textsc{NP}-hard, consider reducing from \textsc{Set-Cover} where there is one node $i$ for each input set $T_i$, $1\leq i\leq n$, with $\neigh{i}= T_i$ and integers $k,\ell$, and the output is ``yes'' if there is a family of $k$ sets in the input which cover at least $\ell$ elements, and ``no'' otherwise. |