Merge branch 'master' of ssh://74.95.195.229:1444/git/data_value

1 files changed, 28 insertions, 47 deletions

diff --git a/main.tex b/main.tex
index f057b4f..1a1d016 100644
--- a/main.tex
+++ b/main.tex
@@ -16,37 +16,28 @@ 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$. We denote by $S_G$ the set constructed by this heuristic. As
-shown in \cite{khuller}, $V(S_G)$ has an unbounded approximation ratio to $OPT$.
-However, let $i^* = \argmax_{i\in\mathcal{N}} V(\{i\})$  be the element of
-maximum value, then defining:
-\begin{displaymath}
-S^* = \left\{
-\begin{aligned}
-\{i^*\}\quad &\textrm{if}\; V(\{i^*\}) \geq V(S_G)\\
-S_G\quad&\textrm{otherwise}
-\end{aligned}\right.,
-\end{displaymath}
-$V(S^*)$ has a bounded approximation to $OPT$. Formally, the following lemma holds.
+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:
 \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:
+$i^* = \argmax_{i\in\mathcal{N}} V(\{i\}).$ We have:
 \begin{displaymath}
 OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
 \end{displaymath}
 \end{lemma}
-This lemma immediately proves an approximation ratio of $\frac{5e}{e-1}$ for
-the afore-mentioned approach. A more sophisticated
-algorithm~\cite{sviridenko-submodular} can attain the optimal $\frac{e}{e-1}$
-approximation ratio
+This lemma immediately implies that the following algorithm:
+\begin{equation}\label{eq:algorithm}
+\textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\}
+\;\textbf{else return}\; S_G
+\end{equation}
+has an approximation ratio of $\frac{5e}{e-1}$.
 
 \subsection*{Submodular maximization in the strategic case}
 
-Following the full information approach, allocating to agent $i^*$ when
-$V(i^*)\geq V(S_G)$ and to $S_G$ otherwise, breaks incentive compatibility.
-Indeed, \citeN{singer-influence} notes that this allocation function is not
-monotone, which implies by Myerson's theorem (Theorem~\ref{thm:myerson}) that
-the resulting mechanism is not truthful.
+In the strategic case, Algorithm~\ref{eq:algorithm} breaks incentive
+compatibility. Indeed, \citeN{singer-influence} notes that this allocation
+function is not monotone, which implies by Myerson's theorem
+(Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful.
 
 Let us denote by $OPT_{-i^*}$ the optimal value achievable in the
 full-information case after removing $i^*$ from the set $\mathcal{N}$:
@@ -56,16 +47,12 @@ full-information case after removing $i^*$ from the set $\mathcal{N}$:
 \end{equation}
 \citeN{singer-mechanisms} and \citeN{chen} prove that using the following
 allocation:
-\begin{displaymath}
-\textrm{allocate to}\quad\left\{
-\begin{aligned}
-i^*\quad&\textrm{if}\; V(i^*)\geq C.OPT_{-i^*} \\
-S_G\quad&\textrm{otherwise}
-\end{aligned}
-\right.
+\begin{displaymath}\label{eq:algorithm}
+\textbf{if}\; V(\{i^*\}) \geq C. OPT_{-i^*}\; \textbf{return}\; \{i^*\}
+\;\textbf{else return}\; S_G
 \end{displaymath}
 yields a 8.34-approximation mechanism for an appropriate $C$ (see also
-Algorithm \ref{mechanism}. However, $OPT_{-i^*}$, the maximum value attainable
+Algorithm~\ref{mechanism}). However, $OPT_{-i^*}$, the maximum value attainable
 in the full-information case, cannot be computed in poly-time when the
 underlying problem is NP-hard (unless P=NP), as is the case for \SEDP{}.
 
@@ -204,10 +191,8 @@ Finally, we prove the approximation ratio of the mechanism. We use the
 following lemma  which establishes that $OPT'$, the optimal value \eqref{relax} of the fractional relaxation $L$ under the budget constraints
  is not too far from $OPT$.  
 \begin{lemma}[Approximation]\label{lemma:relaxation}
-    %\begin{displaymath}
      $   OPT' \leq 2 OPT
         + 2\max_{i\in\mathcal{N}}V(i)$
-    %\end{displaymath}
 \end{lemma}
 The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}.
 
@@ -348,10 +333,8 @@ or the $j$-th component of $\lambda$ becomes integral.
 \begin{proof}
     We give a rounding procedure which, given a feasible $\lambda$ with at least
     two fractional components, returns some feasible $\lambda'$ with one less fractional
-    component such that:
-    \begin{displaymath}
-        F(\lambda) \leq F(\lambda')
-    \end{displaymath}
+    component such that $F(\lambda) \leq F(\lambda')$.
+
     Applying this procedure recursively yields the lemma's result.
     Let us consider such a feasible $\lambda$. Let $i$ and $j$ be two
     fractional components of $\lambda$ and let us define the following
@@ -473,11 +456,11 @@ Using this,
         =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i
     \end{displaymath}
 
-For two symmetric matrices $A$ and $B$, we write $A\succ B$ ($A\succeq B$) if $A-B$ is positive definite (positive semi-definite).
-This order allows us to define the notion of a \emph{decreasing} as well as  \emph{convex}
-matrix function, similarly to their real counterparts. In particular, 
-  matrix inversion is decreasing and convex over symmetric
-positive definite matrices.
+For two symmetric matrices $A$ and $B$, we write $A\succ B$ ($A\succeq B$) if
+$A-B$ is positive definite (positive semi-definite).  This order allows us to
+define the notion of a \emph{decreasing} as well as  \emph{convex} matrix
+function, similarly to their real counterparts. With this definition, matrix
+inversion is decreasing and convex over symmetric positive definite matrices.
 In particular,
 \begin{gather*}
         \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}
@@ -507,11 +490,9 @@ In particular,
         P_\mathcal{N}^\lambda(S)
         \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)
     \end{align*}
-    Using that $A(S)\succeq I_d$ we get that:
-    \begin{displaymath}
-        \T{x_i}A(S)^{-1}x_i \leq \norm{x_i}_2^2 \leq 1 
-    \end{displaymath}
-    Moreover, $\log(1+x)\geq x$ for all $x\leq 1$. Hence:
+    Using that $A(S)\succeq I_d$ we get that $\T{x_i}A(S)^{-1}x_i \leq
+    \norm{x_i}_2^2 \leq 1$. Moreover, $\log(1+x)\geq x$ for all $x\leq 1$.
+    Hence:
     \begin{displaymath}
         \partial_i F(\lambda) \geq
         \frac{1}{4}
@@ -576,7 +557,7 @@ Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*)
     \begin{displaymath}
         F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\})
     \end{displaymath}
-    Using the submodularity of $V$:
+    By submodularity of $V$, $V(S\cup\{i\})\leq V(S) + V(\{i\})$, hence:
     \begin{displaymath}
         F(\bar{\lambda}) \leq V(S) + V(i)
     \end{displaymath}