diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 53 |
1 files changed, 42 insertions, 11 deletions
@@ -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: |