diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 68 |
1 files changed, 27 insertions, 41 deletions
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}. +the proof of the lemma. \qed +%\end{proof} -\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} +%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]$ |