diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 8 |
1 files changed, 4 insertions, 4 deletions
@@ -36,7 +36,7 @@ set). It has been noted by Khuller 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. In the general case, we have the following result from Singer \cite{singer-influence} which follows from -Bei et al. \cite{chen}: +Chen et al. \cite{chen}: \begin{lemma}[Singer \cite{singer-influence}]\label{lemma:greedy-bound} Let $S_G$ be the set computed by the greedy heuristic and let us define $i^*$: @@ -67,10 +67,10 @@ $V(S_G)$ while maintaining the monotonicity of the allocation algorithm. Furthermore, it must be computable in polynomial time to keep an overall polynomial complexity for the allocation algorithm. If the underlying non-strategic optimization program \eqref{eq:non-strategic} can be solved in -polynomial time, Bei et al. \cite{chen} prove that allocating to $i^*$ when +polynomial time, Chen et al. \cite{chen} prove that allocating to $i^*$ when $V(i^*) \geq C\cdot OPT(V,\mathcal{N}\setminus\{i^*\}$ (for some constant $C$) and to $S_G$ otherwise yields a 8.34 approximation mechanism. For specific -problems, Bei et al. \cite{chen} for knapsack on one hand, Singer +problems, Chen et al. \cite{chen} for knapsack on one hand, Singer \cite{singer-influence} for maximum coverage on the other hand, instead compare $V(i^*)$ to $OPT(R_{\mathcal{N}\setminus\{i\}}, B)$, where $R_\mathcal{N}$ denotes a fractional relaxation of the function $V$ over the set @@ -95,7 +95,7 @@ $\lambda_i$ or to reject it with probability $1-\lambda_i$: P_\mathcal{N}^\lambda = \prod_{i\in S} \lambda_i \prod_{i\in\mathcal{N}\setminus S} 1 - \lambda_i \end{displaymath} -For knapsack, Bei et al. \cite{chen} directly use the multi-linear extension as +For knapsack, Chen et al. \cite{chen} directly use the multi-linear extension as the relaxation to compare $V(i^*)$ to. For maximum coverage however, the optimal value of the multi-linear extension cannot be computed in polynomial time. Thus, Singer \cite{singer-influence} introduces a second relaxation of |