diff options
| author | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-02-11 19:29:32 -0800 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-02-11 19:29:32 -0800 |
| commit | fca9d9fca8141e104b792ce0b27346d83af71b82 (patch) | |
| tree | 8d7969ccd5ce8f58d1ea6b10f21a569c00176853 /main.tex | |
| parent | fcb7ef2df7ddd557ae689f79f32498dd2c705c01 (diff) | |
| download | recommendation-fca9d9fca8141e104b792ce0b27346d83af71b82.tar.gz | |
small changes
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 4 |
1 files changed, 1 insertions, 3 deletions
@@ -23,7 +23,7 @@ the following 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}$ \cite{chen}. +has a constant approximation ratio \cite{singer-mechanisms}. \subsection{Submodular Maximization in the Strategic Case} @@ -146,8 +146,6 @@ We can now state our main result: \end{theorem} The value of the constant $C$ is given by \eqref{eq:constant} in Section~\ref{sec:proofofmainthm}. - -\fussy In addition, we prove the following simple lower bound. \begin{theorem}\label{thm:lowerbound} There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. |
