From b3d93b68f5d032a4b438400edd26c3282c2ae5d1 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 5 Nov 2012 11:55:19 -0800
Subject: muthu section 5

---
 main.tex | 53 ++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 42 insertions(+), 11 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 384800b..f3939ec 100644
--- a/main.tex
+++ b/main.tex
@@ -40,7 +40,6 @@ following result from Singer \cite{singer-influence} which follows from
 Chen \emph{et al.}~\cite{chen}: \stratis{Is it Singer or Chen? Also, we need to introduce $V(i)$ somewhere...}
 }
 }
-\junk{
 \begin{lemma}~\cite{singer-influence}\label{lemma:greedy-bound}
 Let $S_G$ be the set computed by the greedy algorithm and let 
 %define $i^*$:
@@ -53,11 +52,9 @@ We have:
 OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
 \end{displaymath}
 \end{lemma}
-}
-let
-$i^* = \argmax_{i\in\mathcal{N}} V(i).$
-Taking the maximum between $V(S_G)$ and $V(i^*)$ yields an approximation
-ratio of $\frac{5e}{e-1}$. ~\cite{singer-influence}. However, 
+Thus, 
+taking the maximum between $V(S_G)$ and $V(i^*)$ yields an approximation
+ratio of $\frac{5e}{e-1}$.  However, 
 this approach breaks incentive compatibility and therefore cannot be directly
 applied to the strategic case.~\cite{singer-influence}
 \junk{
@@ -378,10 +375,10 @@ following lemma  which establishes that $OPT'$, the optimal value \eqref{relax}
 The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}.
 
 
-\paragraph{Finishing Proof of }
+\paragraph{Finishing Proof of Theorem~\ref{thm:main} }
 Note that the lower bound $OPT' \geq  OPT
 $ also holds trivially, as $L$ is a fractional relaxation of $V$ over $\mathcal{N}$.
-Using this lemma, we can complete the proof of Theorem~\ref{thm:main} by showing that, %\begin{lemma}\label{lemma:approx}
+Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm:main} by showing that, %\begin{lemma}\label{lemma:approx}
     %C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C
     %(e-1) -10e  +2}\right)\right)
     for any $\varepsilon > 0$, if $OPT_{-i}'$, the optimal value of $L$ when $i^*$ is excluded from $\mathcal{N}$, has been computed to a precision
@@ -449,6 +446,9 @@ This solution is:
     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
 %\end{proof}
+
+
+
 \subsection{Proof of Lemma~\ref{lemma:relaxation}}\label{sec:relaxation}
 %Recall that, since $L$ is a fractional relaxation of  $V$, 
 %\begin{displaymath}
@@ -456,6 +456,8 @@ This solution is:
 %\end{displaymath}
 %However, for the purpose of proving theorem~\ref{thm:main}, we need to bound
 %$L$ from above (up to a multiplicative factor) by $V$. 
+
+\junk{
 To prove Lemma~\ref{lemma:relaxation}, we use the
 \emph{pipage rounding} method of Ageev and Sviridenko~\cite{pipage}, where
 $L$ is first bounded from above by the multi-linear relaxation $F$, which is itself
@@ -463,12 +465,27 @@ subsequently bounded by $V$. While the latter part is general and can be applied
 to the multi-linear extension of any submodular function, the former part is
 specific to our choice for the function $L$.  %and is our main technical contribution (lemma~\ref{lemma:relaxation-ratio}).
 
-We first prove a variant of the $\varepsilon$-convexity of the multi-linear
+The proof has two aspects. The easier part is that $F$ is bounded by $V$.
+This is called  \emph{cross-convexity}  in the literature (see, \emph{e.g.},
+\cite{dughmi}), or $\varepsilon$-convexity by Ageev and Sviridenko~\cite{pipage}. 
+}
+
+
+We prove that our multi-linear function $F$ has a property 
+ which allows to trade one fractional component of the solution for another until
+one of them becomes integral, without losing any value.
+This property is referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.},
+\cite{dughmi}), or $\varepsilon$-convexity by Ageev and Sviridenko~\cite{pipage} .
+\junk{
+
+a variant of the $\varepsilon$-convexity of the multi-linear
 extension \eqref{eq:multilinear} introduced by Ageev and Sviridenko
 \cite{pipage} which allows to trade one fractional component of the solution for another until
 one of them becomes integral, without loosing any value. This property is also
 referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.},
-\cite{dughmi}). Formally, %this property states that 
+\cite{dughmi}). 
+}
+Formally, %this property states that 
 if we define:
 \begin{displaymath}
     \tilde{F}_\lambda(\varepsilon) \defeq F\big(\lambda + \varepsilon(e_i
@@ -539,6 +556,18 @@ a point $\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n
     $\lambda_\varepsilon$ becomes integral.
 \end{proof}
 
+
+Next, we prove the central result of bounding $L$  appropriately in terms of $F$.
+
+\junk{
+To prove Lemma~\ref{lemma:relaxation}, we use the
+\emph{pipage rounding} method of Ageev and Sviridenko~\cite{pipage}, where
+$L$ is first bounded from above by the multi-linear relaxation $F$, which is itself
+subsequently bounded by $V$. While the latter part is general and can be applied
+to the multi-linear extension of any submodular function, the former part is
+specific to our choice for the function $L$.  %and is our main techn
+}
+
 \begin{lemma}\label{lemma:relaxation-ratio}
  %   The following inequality holds:
 For all $\lambda\in[0,1]^{n},$
@@ -700,7 +729,9 @@ Having bound the ratio between the partial derivatives, we now bound the ratio $
     points, for which we know that both relaxations are equal to the value
     function $V$. Hence, the ratio is equal to 1 on the vertices.
 \end{proof}
- To prove Lemma~\ref{lemma:relaxation},   let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*)
+
+\paragraph{Proof of  Lemma~\ref{lemma:relaxation}}
+Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*)
     = OPT'$. By applying Lemma~\ref{lemma:relaxation-ratio}
     and Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most
     one fractional component such that:
-- 
cgit v1.2.3-70-g09d2

