diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 5 |
1 files changed, 4 insertions, 1 deletions
@@ -90,9 +90,12 @@ The function $L$ is well-known to be concave and even self-concordant (see 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. The main challenge +problem, $OPT'_{-i^*}$ satisfies the required monotonicity property. + +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. \begin{algorithm}[t] \caption{Mechanism for \SEDP{}}\label{mechanism} |