diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 25 |
1 files changed, 2 insertions, 23 deletions
@@ -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} |