Typos. There was an error in the proof of lemma 4. Fixing this error changes our

approximation ratio to 12.98 instead of 19.68...

1 files changed, 24 insertions, 25 deletions

diff --git a/main.tex b/main.tex
index 8937f04..8fb9666 100644
--- a/main.tex
+++ b/main.tex
@@ -92,7 +92,7 @@ $\id_S$ denotes the indicator vector of $S$. The optimization program
     \leq B\right\}\label{relax}
 \end{align}
 Substituting $OPT'_{-i^*}$ for $OPT_{-i^*}$ like before works for specific problems like \textsc{Knapsack}~\cite{chen} and 
-\textsc{Coverage}~\cite{singer-influence}. For other instances of sub modular function, this overall technology
+\textsc{Coverage}~\cite{singer-influence}. For other instances of submodular function, this overall technology
 has to be applied and extended.
 \end{itemize}
 
@@ -257,9 +257,9 @@ We can now state our main result:
     \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that:
     \begin{align*}
         OPT
-        & \leq \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)} V(S^*)+
+        & \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+
         \varepsilon\\
-        & \simeq 19.68V(S^*) + \varepsilon
+        & \simeq 12.98V(S^*) + \varepsilon
     \end{align*}
 \end{theorem}
 
@@ -296,7 +296,7 @@ contribution; the proof of this lemma can be found in Section~\ref{sec:relaxatio
     $O(\text{poly}(n, d))$ and the mechanism only involves a linear
     number of queries to the function $V$. 
     The function $\log\det$ is concave and self-concordant (see
-    \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be find
+    \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be found
     to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$  of iterations of Newton's method. Each iteration  can be
     done in time $O(\text{poly}(n, d))$. Thus, line 3 of
     Algorithm~\ref{mechanism} can be computed in time
@@ -315,7 +315,7 @@ following lemma  which establishes that $OPT'$, the optimal value \eqref{relax}
  is not too far from $OPT$.  
 \begin{lemma}\label{lemma:relaxation}
     %\begin{displaymath}
-     $   OPT' \leq 4 OPT
+     $   OPT' \leq 2 OPT
         + 2\max_{i\in\mathcal{N}}V(i)$
     %\end{displaymath}
 \end{lemma}
@@ -331,7 +331,7 @@ Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm
     $\varepsilon$, then the set $S^*$ allocated by the mechanism is such that:
     \begin{align}
         OPT
-         \leq \frac{14e\!-\!3 + \sqrt{160e^2\!-\!48e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound}
+         \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound}
     \end{align}
 %\end{lemma}
     To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to $\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume that on line 3 of algorithm~\ref{mechanism}, a quantity
@@ -355,39 +355,39 @@ Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm
     from Lemmas \ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
     \begin{align*}
         V(i^*) & \stackrel{}\leq \frac{1}{C}OPT_{-i^*}'+ \frac{\varepsilon}{C}\leq \frac{1}{C}
-        \big(4 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\
-        & \leq \frac{1}{C}\left(\frac{4e}{e-1}\big(3 V(S_G)
+        \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\
+        & \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G)
         + 2 V(i^*)\big)
         + 2 V(i^*)\right) + \frac{\varepsilon}{C}
     \end{align*}
-    Thus, if $C$ is such that $C(e-1) -10e  +2 > 0$,
+    Thus, if $C$ is such that $C(e-1) -6e  +2 > 0$,
     \begin{align*}
-        V(i^*) \leq \frac{12e}{C(e-1)- 10e + 2} V(S_G) 
-        + \frac{(e-1)\varepsilon}{C(e-1)- 10e + 2}
+        V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) 
+        + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}
     \end{align*}
     Finally, using again Lemma~\ref{lemma:greedy-bound}, we get:
     \begin{multline}\label{eq:bound2}
-        OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{8e}{C
-        (e-1) -10e  +2}\right) V(S_G)\\
-        +\frac{2e\varepsilon}{C(e-1)- 10e + 2}
+        OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{4e}{C
+        (e-1) -6e  +2}\right) V(S_G)\\
+        +\frac{2e\varepsilon}{C(e-1)- 6e + 2}
     \end{multline}
     To minimize the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1} and \eqref{eq:bound2} respectively,
     we wish to chose for $C=C^*$ such that:
     \begin{displaymath}
         C^* = \argmin_C 
-        \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C (e-1) -10e  +2}
+        \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}
         \right)\right)
     \end{displaymath}
-    This equation has two solutions. Only one of those is such that:
-      $  C(e-1) -10e  +2 \geq 0$.
+    This equation has two solutions. Only one of those is such that 
+      $C(e-1) -6e  +2 \geq 0$.
     %which is needed in the above derivation. 
 This solution is:
     \begin{align}
-        C^* =  \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)} \label{eq:c}
+        C^* =  \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)} \label{eq:c}
     \end{align}
     For this solution,
  %   \begin{displaymath}
-  $      \frac{2e\varepsilon}{C^*(e-1)- 10e + 2}\leq \varepsilon. $
+  $      \frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon. $
  %   \end{displaymath}
     Placing the expression of $C^*$ in \eqref{eq:bound1} and \eqref{eq:bound2}
     gives the approximation ratio in \eqref{approxbound}, and concludes the proof of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed
@@ -436,7 +436,7 @@ if we define:
     - e_j)\big)
 \end{displaymath}
 where $e_i$ and $e_j$ are two vectors of the standard basis of
-$\reals^{n}$, then $\tilde{F}$ is convex. Hence its maximum over the interval:
+$\reals^{n}$, then $\tilde{F}_\lambda$ is convex. Hence its maximum over the interval:
 \begin{displaymath}
  I_\lambda = \Big[\max(-\lambda_i,\lambda_j-1), \min(1-\lambda_i, \lambda_j)\Big]
 \end{displaymath}
@@ -444,7 +444,7 @@ is attained at one of the boundaries of $I_\lambda$ for which one of the $i$-th
 or the $j$-th component of $\lambda$ becomes integral.
 
 The lemma below proves that we can similarly trade a fractional component for
-an other until one of them becomes integral \emph{while maintaining the
+another until one of them becomes integral \emph{while maintaining the
 feasibility of the point at which $F$ is evaluated}. Here, by feasibility of
 a point $\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n \lambda_i c_i \leq B$.
 \begin{lemma}[Rounding]\label{lemma:rounding}
@@ -697,14 +697,13 @@ Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*)
     \end{equation}
     Let $\lambda_i$ denote the fractional component of $\bar{\lambda}$ and $S$
     denote the set whose indicator vector is $\bar{\lambda} - \lambda_i e_i$.
-    Using the fact that $F$ is linear with respect to the $i$-th
-    component and is a relaxation of the value function, we get:
+    By definition of the multi-linear extension $F$:
     \begin{displaymath}
-        F(\bar{\lambda}) = V(S) +\lambda_i V(S\cup\{i\})
+        F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\})
     \end{displaymath}
     Using the submodularity of $V$:
     \begin{displaymath}
-        F(\bar{\lambda}) \leq 2 V(S) + V(i)
+        F(\bar{\lambda}) \leq V(S) + V(i)
     \end{displaymath}
     Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and
     $V(S)\leq OPT$. Hence: