From 297af7c33e8cc93494cde48212b502f40adc9546 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Wed, 3 Jul 2013 14:59:28 -0700
Subject: approx

---
 appendix.tex | 72 ++++++++++++++++++++++++------------------------------------
 1 file changed, 29 insertions(+), 43 deletions(-)

(limited to 'appendix.tex')

diff --git a/appendix.tex b/appendix.tex
index ca6d1df..67ae7cc 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -1,22 +1,16 @@
-\subsection{Proof of Proposition~\ref{prop:relaxation}}
+\section{Proof of Proposition~\ref{prop:relaxation}}
 
-\begin{lemma}\label{lemma:relaxation-ratio}
-For all $\lambda\in[0,1]^{n},$
-     $           \frac{1}{2}
-        \,L(\lambda)\leq
-        F(\lambda)\leq L(\lambda)$.
-\end{lemma}
-
-\begin{proof}
+\subsection{Proof of Lemma~\ref{lemma:relaxation-ratio}}\label{proofofrelaxation-ratio}
+%\begin{proof}
     The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}}(\lambda)$ follows by the concavity of the $\log\det$ function and Jensen's inequality.
     To show the lower bound, 
     we first prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i
-    F(\lambda)/\partial_i L(\lambda)$, where
-    $\partial_i\, \cdot$ denotes the partial derivative with respect to the
-    $i$-th variable.  
+    F(\lambda)/\partial_i L(\lambda)$, where we use
+    $\partial_i\, \cdot$ as a shorthand for  $\frac{\partial}{\partial \lambda_i}$, the partial derivative  with respect to the
+    $i$-th variable. 
 
-   Let us start by computing the derivatives of $F$ and
-    $L$ with respect to the $i$-th component.
+   Let us start by computing the partial derivatives of $F$ and
+    $L$ with respect to the $i$-th component. 
     Observe that
     \begin{displaymath}
         \partial_i P_\mathcal{N}^\lambda(S) = \left\{
@@ -149,8 +143,8 @@ from below by 1/2 for small enough $\lambda$.
 Second, if the minimum of the ratio $F(\lambda)/L(\lambda)$ is attained at
 a vertex of the hypercube $[0,1]^n$ different from 0. $F$ and $L$ being
 relaxations of the value function $V$, they are equal to $V$ on the vertices
-which are exactly the binary points. Hence the minimum is equal to 1 in this
-case. In particular it is greater than $1/2$.
+which are exactly the binary points. Hence, the minimum is equal to 1 in this
+case; in particular, it is greater than $1/2$.
 
 Finally, if the minimum is attained at a point $\lambda^*$ with at least one
 coordinate belonging to $(0,1)$, let $i$ be one such coordinate and consider
@@ -162,34 +156,26 @@ the function $G_i$:
 Then this function attains a minimum at $\lambda^*_i\in(0,1)$ and its
 derivative is zero at this point. Hence:
 \begin{displaymath}
-    0 = G_i'(\lambda^*_i) = \partial_i\left(\frac{F}{L}\right)(\lambda^*)
-\end{displaymath}.
+    0 = G_i'(\lambda^*_i) = \partial_i\left(\frac{F}{L}\right)(\lambda^*).
+\end{displaymath}
 But $\partial_i(F/L)(\lambda^*)=0$ implies that
 \begin{displaymath}
     \frac{F(\lambda^*)}{L(\lambda^*)} = \frac{\partial_i
     F(\lambda^*)}{\partial_i L(\lambda^*)}\geq \frac{1}{2}
 \end{displaymath}
 using the lower bound on the ratio of the partial derivatives. This concludes
-the proof of the lemma.
-\end{proof}
-
-We now prove that $F$ admits the following exchange property: let
-$\lambda$ be a feasible element of $[0,1]^n$, it is possible to trade one
-fractional component of $\lambda$ for another until one of them becomes
-integral, obtaining a new element $\tilde{\lambda}$ which is both feasible and
-for which $F(\tilde{\lambda})\geq F(\lambda)$. Here, by feasibility of a point
-$\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n
-\lambda_i c_i \leq B$.  This rounding property is referred to in the literature
-as \emph{cross-convexity} (see, \emph{e.g.}, \cite{dughmi}), or
-$\varepsilon$-convexity by \citeN{pipage}.
-
-\begin{lemma}[Rounding]\label{lemma:rounding}
-    For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible
-    $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is
-    fractional %, that is, lies in $(0,1)$ and:
-     and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$.
-\end{lemma}
-
+the proof of the lemma. \qed
+%\end{proof}
+
+%We now prove that $F$ admits the following exchange property: let $\lambda$ be a feasible element of $[0,1]^n$, it is possible to trade one fractional component of $\lambda$ for another until one of them becomes integral, obtaining a new element $\tilde{\lambda}$ which is both feasible and for which $F(\tilde{\lambda})\geq F(\lambda)$. Here, by feasibility of a point $\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n \lambda_i c_i \leq B$.  This rounding property is referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.}, \cite{dughmi}), or $\varepsilon$-convexity by \citeN{pipage}.
+
+%\begin{lemma}[Rounding]\label{lemma:rounding}
+%    For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible
+%    $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is
+%    fractional %, that is, lies in $(0,1)$ and:
+%     and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$.
+%\end{lemma}
+\subsection{Proof of Lemma~\ref{lemma:rounding}}\label{proofoflemmarounding}
 \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
@@ -232,7 +218,7 @@ $\varepsilon$-convexity by \citeN{pipage}.
     $\lambda_\varepsilon$ becomes integral.
 \end{proof}
 
-\subsubsection*{End of the proof of Proposition~\ref{prop:relaxation}}
+\subsection*{End of the proof of Proposition~\ref{prop:relaxation}}
 
 Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that
 $L(\lambda^*) = L^*_c$. By applying Lemma~\ref{lemma:relaxation-ratio} and
@@ -258,7 +244,7 @@ one fractional component such that
     \end{equation}
 Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qedhere
 
-\subsection{Proof of Proposition~\ref{prop:monotonicity}}
+\section{Proof of Proposition~\ref{prop:monotonicity}}
 
 The $\log\det$ function is concave and self-concordant (see
 \cite{boyd2004convex}), in this case, the analysis of the barrier method in
@@ -464,7 +450,7 @@ In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2$.
     with $\lambda^{'*}$ optimal for $(P_{c', \alpha})$. Since $c_i'\leq 1$, using Lemma~\ref{lemma:derivative-bounds}, we get that $\xi^*\geq \frac{b}{2^n}$, which concludes the proof.
 \end{proof}
 
-\subsubsection*{End of the proof of Proposition~\ref{prop:monotonicity}}
+\subsection*{End of the proof of Proposition~\ref{prop:monotonicity}}
 
 Let $\tilde{L}^*_c$ be the approximation computed by
 Algorithm~\ref{alg:monotone}.
@@ -498,7 +484,7 @@ Note that:
 Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed
 \end{enumerate}
 
-\subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
+\section{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
 
 We now present the proof of Theorem~\ref{thm:main}. $\delta$-truthfulness and
 individual rationality follow from $\delta$-monotonicity and threshold
@@ -663,7 +649,7 @@ 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
 
-\subsection{Proof of Theorem \ref{thm:lowerbound}}
+\section{Proof of Theorem \ref{thm:lowerbound}}
 
 Suppose, for contradiction, that such a mechanism exists. Consider two
 experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$
-- 
cgit v1.2.3-70-g09d2

