diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 37 |
1 files changed, 29 insertions, 8 deletions
@@ -21,22 +21,25 @@ This process terminates when no more items can be added to $S$ using \eqref{gree algorithm for \textsc{Knapsack}. However, in contrast to \textsc{Knapsack}, for general submodular functions, the marginal value of an element in \eqref{greedy} depends on the set to which the element is added. Similarly, the value of an element depends on the set in which it is -considered. However, in the following, the value of an element $i$ will refer to -its value as a singleton set: $V(\{i\})$. If there is no ambiguity, we will write -$V(i)$ instead of $V(\{i\})$. - +considered. +%However, in the following, the value of an element $i$ will refer to +%its value as a singleton set: $V(\{i\})$. If there is no ambiguity, we will write +%$V(i)$ instead of $V(\{i\})$. Unfortunately, even for the full information case, the greedy algorithm gives an -unbounded approximation ratio. Let $i^* +unbounded approximation ratio. Instead, we have: +\junk{ + Let $i^* = \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value. % (as a singleton set). %It has been noted by Khuller \emph{et al.}~\cite{khuller} that - For the maximum -coverage problem, taking the maximum between the greedy solution and $V(i^*$) -gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller}. In the general case, +For the maximum +coverage problem, taking the maximum between the greedy solution and $V(i^*)$ (shorthand for $V(\{i\})$) +gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller}. In the general sub modular case, \junk{we have the following result from Singer \cite{singer-influence} which follows from Chen \emph{et al.}~\cite{chen}: \stratis{Is it Singer or Chen? Also, we need to introduce $V(i)$ somewhere...} } +} \begin{lemma}~\cite{singer-influence}\label{lemma:greedy-bound} Let $S_G$ be the set computed by the greedy algorithm and let @@ -64,7 +67,24 @@ $i^*$, and $i$ is excluded from the allocated set. This violates the monotonicit the allocation function and hence also truthfulness, by Myerson's Theorem. } +For the strategic case, +\begin{itemize} +\iem +When the underlying +full information problem \eqref{eq:non-strategic} can be solved in +polynomial time, Chen et al. \cite{chen} prove that +%$OPT_{-i^*}$, the optimal solution to \eqref{eq:non-strategic} when $i^*$ is excluded from set $\mathcal{N}$, can play the %role of this quantity: that is, +allocating to $i^*$ when +$V(i^*) \geq C\cdot OPT_{-i^*}$ (for some constant $C$) +and to $S_G$ otherwise yields a 8.34-approximation mechanism. However, this is not a poly-time mechanism when the underlying problem is NP hard (unless P=NP), as is the case for \EDP. +\item + + +\end{itemize} + + +\junk{ To address this, Chen \emph{et al.}~\cite{chen} %and Singer~\cite{singer-influence}, introduce a third quantity: if $V(i^*)$ is larger than this quantity, the mechanism allocates to $i^*$, otherwise it allocates to the greedy set $S_G$. @@ -79,6 +99,7 @@ full information problem \eqref{eq:non-strategic} can be solved in polynomial time, Chen et al. \cite{chen} prove that $OPT_{-i^*}$, the optimal solution to \eqref{eq:non-strategic} when $i^*$ is excluded from set $\mathcal{N}$, can play the role of this quantity: that is, allocating to $i^*$ when $V(i^*) \geq C\cdot OPT_{-i^*}$ (for some constant $C$) and to $S_G$ otherwise yields a 8.34-approximation mechanism. However, this is not a poly-time mechanism when the underlying problem is NP hard (unless P=NP), as is the case for \EDP. +} \fussy For NP-hard |