diff options
| -rw-r--r-- | main.tex | 14 | ||||
| -rw-r--r-- | proofs.tex | 20 |
2 files changed, 20 insertions, 14 deletions
@@ -17,21 +17,13 @@ element $i$ to be included is the one which maximizes the \end{align} This is repeated until the sum of costs of elements in $S$ reaches the budget constraint $B$. Denote by $S_G$ the set constructed by this heuristic and let -$i^*$ be the element of maximum value. Then, the following lemma holds: -\begin{lemma}~\cite{chen}\label{lemma:greedy-bound} -Let $S_G$ be the set computed by the greedy algorithm and let -$i^* = \argmax_{i\in\mathcal{N}} V(\{i\}).$ We have: -\begin{displaymath} -OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big). -\end{displaymath} -\end{lemma} - -This lemma immediately implies that the following algorithm: +$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$ be the element of maximum value. Then, +the following algorithm: \begin{equation}\label{eq:max-algorithm} \textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\} \;\textbf{else return}\; S_G \end{equation} -has an approximation ratio of $\frac{5e}{e-1}$. +has an approximation ratio of $\frac{5e}{e-1}$ \cite{chen}. \subsection{Submodular Maximization in the Strategic Case} @@ -32,13 +32,27 @@ The complexity of the mechanism is given by the following lemma. \end{proof} Finally, we prove the approximation ratio of the mechanism. We use the -following lemma which establishes that $OPT'$, the optimal value \eqref{relax} of the fractional relaxation $L$ under the budget constraints - is not too far from $OPT$. +following lemma which establishes that $OPT'$, the optimal value \eqref{relax} +of the fractional relaxation $L$ under the budget constraints is not too far +from $OPT$. \begin{lemma}[Approximation]\label{lemma:relaxation} $ OPT' \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$. \end{lemma} -The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}. +The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, +and can be found in Section \ref{sec:relaxation}. + +We also use the following lemma from \cite{chen} which bounds $OPT$ in terms of +the value of $S_G$, as computed in Algorithm \ref{mechanism}, and $i^*$, the +element of maximum value. + +\begin{lemma}[\cite{chen}] +Let $S_G$ be the set computed in Algorithm \ref{mechanism} and let +$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$. We have: +\begin{displaymath} +OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big). +\end{displaymath} +\end{lemma} Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if |