From 7ff4a4d46dbd64cd8bc7c07d0c7f11f13779443c Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 10 Jun 2013 19:09:15 +0200
Subject: Moving our two main results to a section preceding the introduction
 of our mechanism

---
 main.tex | 25 ++-----------------------
 1 file changed, 2 insertions(+), 23 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index d8635db..21260e1 100644
--- a/main.tex
+++ b/main.tex
@@ -61,16 +61,6 @@ following properties:
     \item $OPT'_{-i^*}$ must be computable in polynomial time.
 \end{itemize}
 
-Such a quantity can be found by considering relaxations of the
-optimization problem \eqref{eq:opt-reduced}. A function $L:[0, 1]^{n}\to\reals_+$ defined on the hypercube  $[0, 1]^{n}$ is a \emph{fractional relaxation} of $V$ over the set
-$\mathcal{N}$ if $L(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S$
-denotes the indicator vector of $S$. The optimization program
-\eqref{eq:non-strategic} extends naturally to such relaxations:
-\begin{align}
-    OPT' \defeq \max_{\lambda\in[0, 1]^{n}}
-    \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
-    \leq B\right\}\label{relax}
-\end{align}
 
 One of the main technical contributions of \citeN{chen} and
 \citeN{singer-influence} is to come up with appropriate such relaxations for
@@ -78,24 +68,13 @@ One of the main technical contributions of \citeN{chen} and
 
 \subsection{Our Approach}
 
-\sloppy
-We introduce a relaxation $L$ specifically tailored to the value function of
-\SEDP:
-\begin{equation}\label{eq:our-relaxation}
-\forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq
-\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right),
-\end{equation}
-The function $L$ is well-known to be concave and even self-concordant (see
-\emph{e.g.}, \cite{boyd2004convex}).  In this case, the analysis of Newton's
-method for self-concordant functions in \cite{boyd2004convex}, shows that
-finding the maximum of $L$ to any precision $\varepsilon$ can be done in
-$O(\log\log\varepsilon^{-1})$ iterations. Being the solution to a maximization
-problem, $OPT'_{-i^*}$ satisfies the required monotonicity property. 
 
+\begin{comment}
 The main challenge
 will be to prove that $OPT'_{-i^*}$, for our relaxation $L$, is close to
 $OPT_{-i^*}$. 
 We show this by establishing that $L$ is within a constant factor from the so-called multi-linear relaxation of  \eqref{modified}, which in turn can be related to \eqref{modified} through pipage rounding. We establish the constant factor to the multi-linear relaxation by bounding  the partial derivatives of these two functions; we obtain the latter bound by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices.
+\end{comment}
 
 \begin{algorithm}[t]
     \caption{Mechanism for \SEDP{}}\label{mechanism}
-- 
cgit v1.2.3-70-g09d2

