From bbf9c47b9fc6870a1e755adfa97cd3a688a0478a Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 11 Feb 2013 11:45:10 -0800
Subject: Some fixes to main and proof sections

---
 main.tex | 29 +++++++++++++++++------------
 1 file changed, 17 insertions(+), 12 deletions(-)

(limited to 'main.tex')

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
-- 
cgit v1.2.3-70-g09d2