diff options
| -rw-r--r-- | main.tex | 30 |
1 files changed, 19 insertions, 11 deletions
@@ -18,11 +18,12 @@ Unfortunately, even for the non-strategic case, the greedy heuristic gives an unbounded approximation ratio. It has been noted by Khuller et al. \cite{khuller} that for the maximum coverage problem, taking the maximum between the greedy solution and the point of maximum value gives -a $\frac{2e}{e-1}$ approximation ration. In the general case, lemma 3.1 from +a $\frac{2e}{e-1}$ approximation ratio. In the general case, lemma 3.1 from \cite{singer-influence} which follows from \cite{chen}, shows that this has an -approximation ratio of $\frac{5e}{e-1}$. However, Singer -\cite{singer-influence} notes that this approach breaks incentive compatibility -and therefore cannot be directly applied to the strategic case. +approximation ratio of $\frac{5e}{e-1}$ (see lemma~\ref{lemma:greedy-bound} +below). However, Singer \cite{singer-influence} notes that this approach breaks +incentive compatibility and therefore cannot be directly applied to the +strategic case. Two approaches have been studied to deal with the strategic case and rely on comparing the point of maximum value to a quantity which can be proven to be @@ -168,7 +169,18 @@ readibility, the proof is postponed to section~\ref{sec:relaxation}. \end{displaymath} \end{lemma} -\begin{lemma} +Let us recall here the following lemma from \cite{chen} which we use in the +proof of lemma~\ref{lemma:approx}. This lemma shows, as mentioned above, that +taking the maximum between the greedy solution and the point of maximum value +gives a $\frac{5e}{e-1}$ approximation ratio. +\begin{lemma}\label{lemma:greedy-bound} +The following inequality holds: +\begin{displaymath} + OPT(V,\mathcal{N},B) \leq \frac{5e}{e-1}\max\big( V(S_M), V(i^*)\big) +\end{displaymath} +\end{lemma} + +\begin{lemma}\label{lemma:approx} Let us denote by $S_M$ the set returned by the mechanism. Let us also write: \begin{displaymath} @@ -183,6 +195,7 @@ readibility, the proof is postponed to section~\ref{sec:relaxation}. \end{displaymath} \end{lemma} + \begin{proof} If the condition on line 3 of the algorithm holds, then: @@ -215,12 +228,7 @@ readibility, the proof is postponed to section~\ref{sec:relaxation}. V(i^*) \leq \frac{6e}{C\cdot C_\mu(e-1)- 5e + 1} V(S_M) \end{align*} - Finally, using again that: - \begin{displaymath} - OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big(3 V(S_M) + 2 V(i^*)\big) - \end{displaymath} - - We get: + Finally, using again lemma~\ref{lemma:greedy-bound}, we get: \begin{displaymath} OPT(V, \mathcal{N}, B) \leq \frac{e}{e-1}\left( 3 + \frac{12e}{C\cdot C_\mu(e-1) -5e +1}\right) V(S_M) |