From 62c98a8cc5c9f3feb18ccc4ccc2c5d11d850c020 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sat, 6 Jul 2013 13:47:50 -0700 Subject: linear constraints --- intro.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'intro.tex') diff --git a/intro.tex b/intro.tex index 3a2925b..4d8b5dd 100644 --- a/intro.tex +++ b/intro.tex @@ -64,7 +64,7 @@ We note that the objective \eqref{obj} is submodular. Using this fact, applying From a technical perspective, we propose a convex optimization problem and establish that its optimal value within a constant factor from the optimal value of \EDP. In particular, we show our relaxed objective is within a constant factor from the so-called multi-linear extension of \eqref{obj}, which in turn can be related to \eqref{obj} through pipage rounding. We establish the constant factor to the multi-linear extension by bounding the partial derivatives of these two functions; we achieve the latter by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices. -Our convex relaxation of \EDP{} involves maximizing a self-concordant function subject to linear constraints. Its optimal value can be computed with arbitrary accuracy in polynomial time using the so-called barrier method. However, the outcome of this computation may not nevessarily be monotone, a property needed in designing a truthful mechanism. Nevetheless, we construct an algorithm that solves the above convex relaxation and is ``almost'' monotone; in turn, we also show that this algorithm can be employed to design a $\delta$-truthful mechanism for \EDP{}. +Our convex relaxation of \EDP{} involves maximizing a self-concordant function subject to linear constraints. Its optimal value can be computed with arbitrary accuracy in polynomial time using the so-called barrier method. However, the outcome of this computation may not necessarily be monotone, a property needed in designing a truthful mechanism. Nevetheless, we construct an algorithm that solves the above convex relaxation and is ``almost'' monotone; in turn, we also show that this algorithm can be employed to design a $\delta$-truthful mechanism for \EDP{}. %This allows us to adopt the approach followed by prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}. %{\bf FIX the last sentence} -- cgit v1.2.3-70-g09d2