From 73a47224ff0c5825efe0435db600774b037fb5bf Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Fri, 6 Mar 2015 18:16:03 -0500
Subject: Final version

---
 paper/sections/model.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'paper/sections/model.tex')

diff --git a/paper/sections/model.tex b/paper/sections/model.tex
index ee24eec..5d64acf 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 the full version of the paper~\cite{full}.
+\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}.
 %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.
-- 
cgit v1.2.3-70-g09d2

