diff options
| author | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2012-11-04 16:18:02 -0800 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2012-11-04 16:18:02 -0800 |
| commit | b27a1e52745d710e78bfc7097496b35a70388629 (patch) | |
| tree | 404a22f9654e979fc7750dd202d1fe0c499ba223 /main.tex | |
| parent | 340d8855e7dd38e6c9fef2a8ea81f0418677343d (diff) | |
| download | recommendation-b27a1e52745d710e78bfc7097496b35a70388629.tar.gz | |
proof intro
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 12 |
1 files changed, 5 insertions, 7 deletions
@@ -182,12 +182,10 @@ Suppose, for contradiction, that such a mechanism exists. Consider two experimen %The proof of the properties of the mechanism is broken down into lemmas. We now present the proof of Theorem~\ref{thm:main}. -Monotonicity and budget feasibility follows from the analysis of Chen \emph{et al.}; we briefly restate the proofs for the sake of completeness. -\cite{chen}. The proof of the approximation ratio is done in -lemma~\ref{lemma:approx} and uses a bound on our concave relaxation -$L_\mathcal{N}$ (lemma~\ref{lemma:relaxation}) which is our main technical -contribution. The proof of this lemma is done in a dedicated section -(\ref{sec:relaxation}). +Monotonicity and budget feasibility follows from the analysis of Chen \emph{et al.} \cite{chen}; we briefly restate the proofs for the sake of completeness. + Our proof of the approximation ratio and uses a bound on our concave relaxation +$L_\mathcal{N}$ (Lemma~\ref{lemma:relaxation}). This is our main technical +contribution; the proof of this lemma can be found in Section~\ref{sec:relaxation}. \begin{lemma}\label{lemma:monotone} The mechanism is monotone. @@ -342,7 +340,7 @@ 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} +\subsection{Proof of Lemma~\ref{lemma:relaxation}}\label{sec:relaxation} Since $L_\mathcal{N}$ is a relaxation of the value function $V$, we have: \begin{displaymath} |
