Some fixes to main and proof sections

2 files changed, 35 insertions, 23 deletions

diff --git a/main.tex b/main.tex
index 2986eb1..7e9fe02 100644
--- a/main.tex
+++ b/main.tex
@@ -2,7 +2,7 @@
 
 In this section we present our mechanism for \SEDP. Prior approaches to budget
 feasible mechanisms for sudmodular maximization build upon the full information
-case which we discuss first.
+case, which we discuss first.
 
 \subsection{Submodular Maximization in the Full Information Case}
 
@@ -16,8 +16,8 @@ element $i$ to be included is the one which maximizes the
     i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy}
 \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 by
-$i^* = \argmax_{i\in\mathcal{N}} V(\{i\})$, then the following lemma holds:
+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:
@@ -25,6 +25,7 @@ $i^* = \argmax_{i\in\mathcal{N}} V(\{i\}).$ We have:
 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:
 \begin{equation}\label{eq:max-algorithm}
 \textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\}
@@ -45,10 +46,10 @@ full-information case after removing $i^*$ from the set $\mathcal{N}$:
     OPT_{-i^*} \defeq \max_{S\subseteq\mathcal{N}\setminus\{i^*\}} \Big\{V(S) \;\Big| \;
     \sum_{i\in S}c_i\leq B\Big\}
 \end{equation}
-\citeN{singer-mechanisms} and \citeN{chen} prove that using the following
+\citeN{singer-mechanisms} and \citeN{chen} prove that the following
 allocation:
 \begin{displaymath}
-\textbf{if}\; V(\{i^*\}) \geq C. OPT_{-i^*}\; \textbf{return}\; \{i^*\}
+\textbf{if}\; V(\{i^*\}) \geq C \cdot OPT_{-i^*}\; \textbf{return}\; \{i^*\}
 \;\textbf{else return}\; S_G
 \end{displaymath}
 yields a 8.34-approximation mechanism for an appropriate $C$ (see also
@@ -79,9 +80,9 @@ denotes the indicator vector of $S$. The optimization program
     \leq B\right\}\label{relax}
 \end{align}
 
-One of the main technical contribution of \citeN{chen} and
-\citeN{singer-influence} is to come up with appropriate relaxations for
-\textsc{Knapsack} and \textsc{Coverage} respectively.
+One of the main technical contributions of \citeN{chen} and
+\citeN{singer-influence} is to come up with appropriate such relaxations for
+\textsc{Knapsack} and \textsc{Coverage}, respectively.
 
 \subsection{Our Approach}
 
@@ -98,7 +99,8 @@ method for self-concordant functions in \cite{boyd2004convex}, shows that
 finding the maximum of $L$ to any precision $\varepsilon$ can be done in
 $O(\log\log\varepsilon^{-1})$ iterations. Being the solution to a maximization
 problem, $L^*$ satisfies the required monotonicity property. The main challenge
-will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to $OPT$. 
+will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to
+$OPT_{-i^*}$. 
 
 \begin{algorithm}[t]
     \caption{Mechanism for \SEDP{}}\label{mechanism}
@@ -138,9 +140,10 @@ be found in~\cite{singer-mechanisms}.
 We can now state our main result:
 \begin{theorem}\label{thm:main}
     \sloppy
-    The allocation described in Algorithm~\ref{mechanism}, along with threshold payments, is truthful, individually rational 
-    and budget feasible. Furthermore, for any $\varepsilon>0$, the mechanism
-  runs in time  $O\left(\text{poly}(n, d,
+    The allocation described in Algorithm~\ref{mechanism}, along with threshold
+    payments, is truthful, individually rational and budget feasible.
+    Furthermore, there exists an absolute constant $C$ such that, for any
+    $\varepsilon>0$, the mechanism runs in time  $O\left(\text{poly}(n, d,
     \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that:
     \begin{align*}
         OPT
@@ -148,6 +151,8 @@ We can now state our main result:
         \varepsilon\\
         & \simeq 12.98V(S^*) + \varepsilon
     \end{align*}
+    The value of the constant $C$ is given by \eqref{eq:constant} in
+    Section~\ref{sec:proofofmainthm}.
 \end{theorem}
 
 \fussy
diff --git a/proofs.tex b/proofs.tex
index ba22501..eb1226c 100644
--- a/proofs.tex
+++ b/proofs.tex
@@ -6,10 +6,12 @@ budget feasibility follow the same steps as the analysis of \citeN{chen};
  for the sake of completeness, we restate their proof in the Appendix.
 
 The complexity of the mechanism is given by the following lemma.
+
 \begin{lemma}[Complexity]\label{lemma:complexity}
     For any $\varepsilon > 0$, the complexity of the mechanism  is
     $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$.
 \end{lemma}
+
 \begin{proof}
     The value function $V$ in \eqref{modified} can be computed in time
     $O(\text{poly}(n, d))$ and the mechanism only involves a linear
@@ -50,11 +52,12 @@ OPT
 \end{equation}
 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 $\tilde{L}$ such that
+that on line 3 of Algorithm~\ref{mechanism}, a quantity $\tilde{L}$ such that
 $\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq \tilde{L}+\varepsilon$ has been
 computed (Lemma~\ref{lemma:complexity} states that this  is computed in time
-within our complexity guarantee).  If the condition on line 3 of the algorithm
-holds, then:
+within our complexity guarantee).
+
+If the condition on line 3 of the algorithm holds, then:
 \begin{displaymath}
     V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq
     \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C} 
@@ -64,20 +67,24 @@ hence:
 \begin{equation}\label{eq:bound1}
     OPT\leq (1+C)V(i^*) + \varepsilon
 \end{equation}
-Note that $OPT_{-i^*}'\leq OPT'$. If the condition  does not hold, 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(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\
-    & \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G)
+
+If the condition  does not hold, by observing that $OPT'_{-i^*}\leq OPT'$ and
+applying Lemma~\ref{lemma:relaxation}, we get:
+\begin{displaymath}
+    V(i^*)  \stackrel{}\leq \frac{1}{C}OPT_{-i^*}' + \frac{\varepsilon}{C}
+    \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}
+\end{displaymath}
+Applying Lemma~\ref{lemma:greedy-bound}:
+\begin{displaymath}
+    V(i^*) \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*}
+\end{displaymath}
 Thus, if $C$ is such that $C(e-1) -6e  +2 > 0$,
 \begin{align*}
     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:
+Finally, using Lemma~\ref{lemma:greedy-bound} again, we get:
 \begin{equation}\label{eq:bound2}
     OPT(V, \mathcal{N}, B) \leq 
     \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e  +2}\right) V(S_G)