\subsection{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} The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}(\lambda)}$ follows by the concavity of the $\log\det$ function. 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. Let us start by computing the derivatives of $F$ and $L$ with respect to the $i$-th component. Observe that \begin{displaymath} \partial_i P_\mathcal{N}^\lambda(S) = \left\{ \begin{aligned} & P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})\;\textrm{if}\; i\in S, \\ & - P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\;\textrm{if}\; i\in \mathcal{N}\setminus S. \\ \end{aligned}\right. \end{displaymath} Hence, \begin{displaymath} \partial_i F(\lambda) = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})V(S) - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S). \end{displaymath} Now, using that every $S$ such that $i\in S$ can be uniquely written as $S'\cup\{i\}$, we can write: \begin{displaymath} \partial_i F(\lambda) = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\big(V(S\cup\{i\}) - V(S)\big). \end{displaymath} The marginal contribution of $i$ to $S$ can be written as \begin{align*} V(S\cup \{i\}) - V(S)& = \frac{1}{2}\log\det(I_d + \T{X_S}X_S + x_i\T{x_i}) - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\\ & = \frac{1}{2}\log\det(I_d + x_i\T{x_i}(I_d + \T{X_S}X_S)^{-1}) = \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i) \end{align*} where $A(S) \defeq I_d+ \T{X_S}X_S$, and the last equality follows from the Sylvester's determinant identity~\cite{sylvester}. % $ V(S\cup\{i\}) - V(S) = \frac{1}{2}\log\left(1 + \T{x_i} A(S)^{-1}x_i\right)$. Using this, \begin{displaymath} \partial_i F(\lambda) = \frac{1}{2} \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big) \end{displaymath} The computation of the derivative of $L$ uses standard matrix calculus: writing $\tilde{A}(\lambda) = I_d+\sum_{i\in \mathcal{N}}\lambda_ix_i\T{x_i}$, \begin{displaymath} \det \tilde{A}(\lambda + h\cdot e_i) = \det\big(\tilde{A}(\lambda) + hx_i\T{x_i}\big) =\det \tilde{A}(\lambda)\big(1+ h\T{x_i}\tilde{A}(\lambda)^{-1}x_i\big). \end{displaymath} Hence, \begin{displaymath} \log\det\tilde{A}(\lambda + h\cdot e_i)= \log\det\tilde{A}(\lambda) + h\T{x_i}\tilde{A}(\lambda)^{-1}x_i + o(h), \end{displaymath} which implies \begin{displaymath} \partial_i L(\lambda) =\frac{1}{2} \T{x_i}\tilde{A}(\lambda)^{-1}x_i. \end{displaymath} For two symmetric matrices $A$ and $B$, we write $A\succ B$ ($A\succeq B$) if $A-B$ is positive definite (positive semi-definite). This order allows us to define the notion of a \emph{decreasing} as well as \emph{convex} matrix function, similarly to their real counterparts. With this definition, matrix inversion is decreasing and convex over symmetric positive definite matrices (see Example 3.48 p. 110 in \cite{boyd2004convex}). In particular, \begin{gather*} \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1} \end{gather*} as $A(S)\preceq A(S\cup\{i\})$. Observe that % \begin{gather*} % \forall $P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})$ for all $S\subseteq\mathcal{N}\setminus\{i\}$, and % ,\\ $P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \geq P_\mathcal{N}^\lambda(S),$ for all $S\subseteq\mathcal{N}$. %\end{gather*} Hence, \begin{align*} \partial_i F(\lambda) % & = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_\mathcal{N}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\ & \geq \frac{1}{4} \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\ &\hspace{-3.5em}+\frac{1}{4} \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\}) \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\ &\geq \frac{1}{4} \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big). \end{align*} Using that $A(S)\succeq I_d$ we get that $\T{x_i}A(S)^{-1}x_i \leq \norm{x_i}_2^2 \leq 1$. Moreover, $\log(1+x)\geq x$ for all $x\leq 1$. Hence, \begin{displaymath} \partial_i F(\lambda) \geq \frac{1}{4} \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)^{-1}\bigg)x_i. \end{displaymath} Finally, using that the inverse is a matrix convex function over symmetric positive definite matrices: \begin{displaymath} \partial_i F(\lambda) \geq \frac{1}{4} \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i = \frac{1}{4}\T{x_i}\tilde{A}(\lambda)^{-1}x_i = \frac{1}{2} \partial_i L(\lambda). \end{displaymath} Having bound the ratio between the partial derivatives, we now bound the ratio $F(\lambda)/L(\lambda)$ from below. Consider the following cases. First, if the minimum of the ratio $F(\lambda)/L(\lambda)$ is attained at a point interior to the hypercube, then it is a critical point, \emph{i.e.}, $\partial_i \big(F(\lambda)/L(\lambda)\big)=0$ for all $i\in \mathcal{N}$; hence, at such a critical point: \begin{equation}\label{eq:lhopital} \frac{F(\lambda)}{L(\lambda)} = \frac{\partial_i F(\lambda)}{\partial_i L(\lambda)} \geq \frac{1}{2}. \end{equation} Second, if the minimum is attained as $\lambda$ converges to zero in, \emph{e.g.}, the $l_2$ norm, by the Taylor approximation, one can write: \begin{displaymath} \frac{F(\lambda)}{L(\lambda)} \sim_{\lambda\rightarrow 0} \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F(0)} {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L(0)} \geq \frac{1}{2}, \end{displaymath} \emph{i.e.}, the ratio $\frac{F(\lambda)}{L(\lambda)}$ is necessarily bounded from below by 1/2 for small enough $\lambda$. Finally, if the minimum is attained on a face of the hypercube $[0,1]^n$ (a face is defined as a subset of the hypercube where one of the variable is fixed to 0 or 1), without loss of generality, we can assume that the minimum is attained on the face where the $n$-th variable has been fixed to 0 or 1. Then, either the minimum is attained at a point interior to the face or on a boundary of the face. In the first sub-case, relation \eqref{eq:lhopital} still characterizes the minimum for $i< n$. In the second sub-case, by repeating the argument again by induction, we see that all is left to do is to show that the bound holds for the vertices of the cube (the faces of dimension 1). The vertices are exactly the binary points, for which we know that both relaxations are equal to the value function $V$. Hence, the ratio is equal to 1 on the vertices. \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}. \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} \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 component such that $F(\lambda) \leq F(\lambda')$. Applying this procedure recursively yields the lemma's result. Let us consider such a feasible $\lambda$. Let $i$ and $j$ be two fractional components of $\lambda$ and let us define the following function: \begin{displaymath} F_\lambda(\varepsilon) = F(\lambda_\varepsilon) \quad\textrm{where} \quad \lambda_\varepsilon = \lambda + \varepsilon\left(e_i-\frac{c_i}{c_j}e_j\right) \end{displaymath} It is easy to see that if $\lambda$ is feasible, then: \begin{equation}\label{eq:convex-interval} \forall\varepsilon\in\Big[\max\Big(-\lambda_i,(\lambda_j-1)\frac{c_j}{c_i}\Big), \min\Big(1-\lambda_i, \lambda_j \frac{c_j}{c_i}\Big)\Big],\; \lambda_\varepsilon\;\;\textrm{is feasible} \end{equation} Furthermore, the function $F_\lambda$ is convex; indeed: \begin{align*} F_\lambda(\varepsilon) & = \mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[ (\lambda_i+\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i,j\})\\ & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\}) + (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\ & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big] \end{align*} Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is: \begin{displaymath} \frac{c_i}{c_j}\mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[ V(S'\cup\{i\})+V(S'\cup\{i\})\\ -V(S'\cup\{i,j\})-V(S')\Big] \end{displaymath} which is positive by submodularity of $V$. Hence, the maximum of $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is attained at one of its limit, at which either the $i$-th or $j$-th component of $\lambda_\varepsilon$ becomes integral. \end{proof} \subsubsection*{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 Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most one fractional component such that \begin{equation}\label{eq:e1} L(\lambda^*) \leq 2 F(\bar{\lambda}). \end{equation} Let $\lambda_i$ denote the fractional component of $\bar{\lambda}$ and $S$ denote the set whose indicator vector is $\bar{\lambda} - \lambda_i e_i$. By definition of the multi-linear extension $F$: \begin{displaymath} F(\bar{\lambda}) = (1-\lambda_i)V(S) +\lambda_i V(S\cup\{i\}). \end{displaymath} By submodularity of $V$, $V(S\cup\{i\})\leq V(S) + V(\{i\})$. Hence, \begin{displaymath} F(\bar{\lambda}) \leq V(S) + V(i). \end{displaymath} Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and $V(S)\leq OPT$. Hence, \begin{equation}\label{eq:e2} F(\bar{\lambda}) \leq OPT + \max_{i\in\mathcal{N}} V(i). \end{equation} Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qedhere \subsection{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 in \cite{boyd2004convex} (Section 11.5.5) can be summarized in the following lemma: \begin{lemma}\label{lemma:barrier} For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$. \end{lemma} We show that the optimal value of \eqref{eq:perturbed-primal} is close to the optimal value of \eqref{eq:primal} (Lemma~\ref{lemma:proximity}) while being well-behaved with respect to changes of the cost (Lemma~\ref{lemma:monotonicity}). These lemmas together imply Proposition~\ref{prop:monotonicity}. \begin{lemma}\label{lemma:derivative-bounds} Let $\partial_i L(\lambda)$ denote the $i$-th derivative of $L$, for $i\in\{1,\ldots, n\}$, then: \begin{displaymath} \forall\lambda\in[0, 1]^n,\;\frac{b}{2^n} \leq \partial_i L(\lambda) \leq 1 \end{displaymath} \end{lemma} \begin{proof} Recall that we had defined: \begin{displaymath} \tilde{A}(\lambda)\defeq I_d + \sum_{i=1}^n \lambda_i x_i\T{x_i} \quad\mathrm{and}\quad A(S) \defeq I_d + \sum_{i\in S} x_i\T{x_i} \end{displaymath} Let us also define $A_k\defeq A(\{x_1,\ldots,x_k\})$. We have $\partial_i L(\lambda) = \T{x_i}\tilde{A}(\lambda)^{-1}x_i$. Since $\tilde{A}(\lambda)\succeq I_d$, $\partial_i L(\lambda)\leq \T{x_i}x_i \leq 1$, which is the right-hand side of the lemma. For the left-hand side, note that $\tilde{A}(\lambda) \preceq A_n$. Hence $\partial_iL(\lambda)\geq \T{x_i}A_n^{-1}x_i$. Using the Sherman-Morrison formula, for all $k\geq 1$: \begin{displaymath} \T{x_i}A_k^{-1} x_i = \T{x_i}A_{k-1}^{-1}x_i - \frac{(\T{x_i}A_{k-1}^{-1}x_k)^2}{1+\T{x_k}A_{k-1}^{-1}x_k} \end{displaymath} By the Cauchy-Schwarz inequality: \begin{displaymath} (\T{x_i}A_{k-1}^{-1}x_k)^2 \leq \T{x_i}A_{k-1}^{-1}x_i\;\T{x_k}A_{k-1}^{-1}x_k \end{displaymath} Hence: \begin{displaymath} \T{x_i}A_k^{-1} x_i \geq \T{x_i}A_{k-1}^{-1}x_i - \T{x_i}A_{k-1}^{-1}x_i\frac{\T{x_k}A_{k-1}^{-1}x_k}{1+\T{x_k}A_{k-1}^{-1}x_k} \end{displaymath} But $\T{x_k}A_{k-1}^{-1}x_k\leq 1$ and $\frac{a}{1+a}\leq \frac{1}{2}$ if $0\leq a\leq 1$, so: \begin{displaymath} \T{x_i}A_{k}^{-1}x_i \geq \T{x_i}A_{k-1}^{-1}x_i - \frac{1}{2}\T{x_i}A_{k-1}^{-1}x_i\geq \frac{\T{x_i}A_{k-1}^{-1}x_i}{2} \end{displaymath} By induction: \begin{displaymath} \T{x_i}A_n^{-1} x_i \geq \frac{\T{x_i}x_i}{2^n} \end{displaymath} Using that $\T{x_i}{x_i}\geq b$ concludes the proof of the left-hand side of the lemma's inequality. \end{proof} Let us introduce the lagrangian of problem, \eqref{eq:perturbed-primal}: \begin{displaymath} \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi) \defeq L(\lambda) + \T{\mu}(\lambda-\alpha\mathbf{1}) + \T{\nu}(\mathbf{1}-\lambda) + \xi(1-\T{c}\lambda) \end{displaymath} so that: \begin{displaymath} L^*_c(\alpha) = \min_{\mu, \nu, \xi\geq 0}\max_\lambda \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi) \end{displaymath} Similarly, we define $\mathcal{L}_{c}\defeq\mathcal{L}_{c, 0}$ the lagrangian of \eqref{eq:primal}. Let $\lambda^*$ be primal optimal for \eqref{eq:perturbed-primal}, and $(\mu^*, \nu^*, \xi^*)$ be dual optimal for the same problem. In addition to primal and dual feasibility, the KKT conditions give $\forall i\in\{1, \ldots, n\}$: \begin{gather*} \partial_i L(\lambda^*) + \mu_i^* - \nu_i^* - \xi^* c_i = 0\\ \mu_i^*(\lambda_i^* - \alpha) = 0\\ \nu_i^*(1 - \lambda_i^*) = 0 \end{gather*} \begin{lemma}\label{lemma:proximity} We have: \begin{displaymath} L^*_c - \alpha n^2\leq L^*_c(\alpha) \leq L^*_c \end{displaymath} In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2$. \end{lemma} \begin{proof} $\alpha\mapsto L^*_c(\alpha)$ is a decreasing function as it is the maximum value of the $L$ function over a set-decreasing domain, which gives the rightmost inequality. Let $\mu^*, \nu^*, \xi^*$ be dual optimal for $(P_{c, \alpha})$, that is: \begin{displaymath} L^*_{c}(\alpha) = \max_\lambda \mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*) \end{displaymath} Note that $\mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*) = \mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*) - \alpha\T{\mathbf{1}}\mu^*$, and that for any $\lambda$ feasible for problem \eqref{eq:primal}, $\mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*) \geq L(\lambda)$. Hence, \begin{displaymath} L^*_{c}(\alpha) \geq L(\lambda) - \alpha\T{\mathbf{1}}\mu^* \end{displaymath} for any $\lambda$ feasible for \eqref{eq:primal}. In particular, for $\lambda$ primal optimal for $\eqref{eq:primal}$: \begin{equation}\label{eq:local-1} L^*_{c}(\alpha) \geq L^*_c - \alpha\T{\mathbf{1}}\mu^* \end{equation} Let us denote by the $M$ the support of $\mu^*$, that is $M\defeq \{i|\mu_i^* > 0\}$, and by $\lambda^*$ a primal optimal point for $\eqref{eq:perturbed-primal}$. From the KKT conditions we see that: \begin{displaymath} M \subseteq \{i|\lambda_i^* = \alpha\} \end{displaymath} Let us first assume that $|M| = 0$, then $\T{\mathbf{1}}\mu^*=0$ and the lemma follows. We will now assume that $|M|\geq 1$. In this case $\T{c}\lambda^* = 1$, otherwise we could increase the coordinates of $\lambda^*$ in $M$, which would increase the value of the objective function and contradict the optimality of $\lambda^*$. Note also, that $|M|\leq n-1$, otherwise, since $\alpha< \frac{1}{n}$, we would have $\T{c}\lambda^*\ < 1$, which again contradicts the optimality of $\lambda^*$. Let us write: \begin{displaymath} 1 = \T{c}\lambda^* = \alpha\sum_{i\in M}c_i + \sum_{i\in \bar{M}}\lambda_i^*c_i \leq \alpha |M| + (n-|M|)\max_{i\in \bar{M}} c_i \end{displaymath} That is: \begin{equation}\label{local-2} \max_{i\in\bar{M}} c_i \geq \frac{1 - |M|\alpha}{n-|M|}> \frac{1}{n} \end{equation} where the last inequality uses again that $\alpha<\frac{1}{n}$. From the KKT conditions, we see that for $i\in M$, $\nu_i^* = 0$ and: \begin{equation}\label{local-3} \mu_i^* = \xi^*c_i - \partial_i L(\lambda^*)\leq \xi^*c_i\leq \xi^* \end{equation} since $\partial_i L(\lambda^*)\geq 0$ and $c_i\leq 1$. Furthermore, using the KKT conditions again, we have that: \begin{equation}\label{local-4} \xi^* \leq \inf_{i\in \bar{M}}\frac{\partial_i L(\lambda^*)}{c_i}\leq \inf_{i\in \bar{M}} \frac{1}{c_i} = \frac{1}{\max_{i\in\bar{M}} c_i} \end{equation} where the last inequality uses Lemma~\ref{lemma:derivative-bounds}. Combining \eqref{local-2}, \eqref{local-3} and \eqref{local-4}, we get that: \begin{displaymath} \sum_{i\in M}\mu_i^* \leq |M|\xi^* \leq n\xi^*\leq \frac{n}{\max_{i\in\bar{M}} c_i} \leq n^2 \end{displaymath} This implies that: \begin{displaymath} \T{\mathbf{1}}\mu^* = \sum_{i=1}^n \mu^*_i = \sum_{i\in M}\mu_i^*\leq n^2 \end{displaymath} which in addition to \eqref{eq:local-1} proves the lemma. \end{proof} \begin{lemma}\label{lemma:monotonicity} If $c'$ = $(c_i', c_{-i})$, with $c_i'\leq c_i - \delta$, we have: \begin{displaymath} L^*_{c'}(\alpha) \geq L^*_c(\alpha) + \frac{\alpha\delta b}{2^n} \end{displaymath} \end{lemma} \begin{proof} Let $\mu^*, \nu^*, \xi^*$ be dual optimal for $(P_{c', \alpha})$. Noting that: \begin{displaymath} \mathcal{L}_{c', \alpha}(\lambda, \mu^*, \nu^*, \xi^*) \geq \mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*) + \lambda_i\xi^*\delta, \end{displaymath} we get similarly to Lemma~\ref{lemma:proximity}: \begin{displaymath} L^*_{c'}(\alpha) \geq L(\lambda) + \lambda_i\xi^*\delta \end{displaymath} for any $\lambda$ feasible for \eqref{eq:perturbed-primal}. In particular, for $\lambda^*$ primal optimal for \eqref{eq:perturbed-primal}: \begin{displaymath} L^*_{c'}(\alpha) \geq L^*_{c}(\alpha) + \alpha\xi^*\delta \end{displaymath} since $\lambda_i^*\geq \alpha$. Using the KKT conditions for $(P_{c', \alpha})$, we can write: \begin{displaymath} \xi^* = \inf_{i:\lambda^{'*}_i>\alpha} \frac{\T{x_i}S(\lambda^{'*})^{-1}x_i}{c_i'} \end{displaymath} 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}} Let $\tilde{L}^*_c$ be the approximation computed by Algorithm~\ref{alg:monotone}. \begin{enumerate} \item using Lemma~\ref{lemma:proximity}: \begin{displaymath} |\tilde{L}^*_c - L^*_c| \leq |\tilde{L}^*_c - L^*_c(\alpha)| + |L^*_c(\alpha) - L^*_c| \leq \alpha\delta + \alpha n^2 = \varepsilon \end{displaymath} which proves the $\varepsilon$-accuracy. \item for the $\delta$-decreasingness, let $c' = (c_i', c_{-i})$ with $c_i'\leq c_i-\delta$, then: \begin{displaymath} \tilde{L}^*_{c'} \geq L^*_{c'} - \frac{\alpha\delta b}{2^{n+1}} \geq L^*_c + \frac{\alpha\delta b}{2^{n+1}} \geq \tilde{L}^*_c \end{displaymath} where the first and inequality come from the accuracy of the approximation, and the inner inequality follows from Lemma~\ref{lemma:monotonicity}. \item the accuracy of the approximation $\tilde{L}^*_c$ is: \begin{displaymath} A\defeq\frac{\varepsilon\delta b}{2^{n+1}(\delta + n^2)} \end{displaymath} Note that: \begin{displaymath} \log\log A^{-1} = O\bigg(\log\log\frac{1}{\varepsilon\delta b} + \log n\bigg) \end{displaymath} 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} We now present the proof of Theorem~\ref{thm:main}. $\delta$-truthfulness and individual rationality follow from $\delta$-monotonicity and threshold payments. $\delta$-monotonicity and budget feasibility follow the same steps as the analysis of \citeN{chen}; for the sake of completeness, we restate their proof here. \begin{lemma}\label{lemma:monotone} Our mechanism for \EDP{} is $\delta$-monotone and budget feasible. \end{lemma} \begin{proof} Consider an agent $i$ with cost $c_i$ that is selected by the mechanism, and suppose that she reports a cost $c_i'\leq c_i-\delta$ while all other costs stay the same. Suppose that when $i$ reports $c_i$, $OPT'_{-i^*} \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$. By reporting cost $c_i'$, $i$ may be selected at an earlier iteration of the greedy algorithm. %using the submodularity of $V$, we see that $i$ will satisfy the greedy %selection rule: %\begin{displaymath} % i = \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\}) % - V(S)}{c_j} %\end{displaymath} %in an earlier iteration of the greedy heuristic. Denote by $S_i$ (resp. $S_i'$) the set to which $i$ is added when reporting cost $c_i$ (resp. $c_i'$). We have $S_i'\subseteq S_i$; in addition, $S_i'\subseteq S_G'$, the set selected by the greedy algorithm under $(c_i',c_{-i})$; if not, then greedy selection would terminate prior to selecting $i$ also when she reports $c_i$, a contradiction. Moreover, we have \begin{align*} c_i' & \leq c_i \leq \frac{B}{2}\frac{V(S_i\cup\{i\})-V(S_i)}{V(S_i\cup\{i\})} \leq \frac{B}{2}\frac{V(S_i'\cup\{i\})-V(S_i')}{V(S_i'\cup\{i\})} \end{align*} by the monotonicity and submodularity of $V$. Hence $i\in S_G'$. By $\delta$-decreasingness of $OPT'_{-i^*}$, under $c'_i\leq c_i-\delta$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$. Suppose now that when $i$ reports $c_i$, $OPT'_{-i^*} < C V(i^*)$. Then $s_i(c_i,c_{-i})=1$ iff $i = i^*$. Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor $OPT'_{-i^*} \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone. To show budget feasibility, suppose that $OPT'_{-i^*} < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible. Suppose that $OPT'_{-i^*} \geq C V(i^*)$. Denote by $S_G$ the set selected by the greedy algorithm, and for $i\in S_G$, denote by $S_i$ the subset of the solution set that was selected by the greedy algorithm just prior to the addition of $i$---both sets determined for the present cost vector $c$. %Chen \emph{et al.}~\cite{chen} show that, Then for any submodular function $V$, and for all $i\in S_G$: %the reported cost of an agent selected by the greedy heuristic, and holds for %any submodular function $V$: \begin{equation}\label{eq:budget} \text{if}~c_i'\geq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B~\text{then}~s_i(c_i',c_{-i})=0 \end{equation} In other words, if $i$ increases her cost to a value higher than $\frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)}$, she will cease to be in the selected set $S_G$. As a result, \eqref{eq:budget} implies that the threshold payment of user $i$ is bounded by the above quantity. %\begin{displaymath} %\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} = B %\end{displaymath} Hence, the total payment is bounded by the telescopic sum: \begin{displaymath} \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qed \end{displaymath} \end{proof} The complexity of the mechanism is given by the following lemma. \begin{lemma}[Complexity]\label{lemma:complexity} For any $\varepsilon > 0$ and any $\delta>0$, the complexity of the mechanism is $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$ \end{lemma} \begin{proof} The value function $V$ in \eqref{modified} can be computed in time $O(\text{poly}(n, d))$ and the mechanism only involves a linear number of queries to the function $V$. By Proposition~\ref{prop:monotonicity}, line 3 of Algorithm~\ref{mechanism} can be computed in time $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. Hence the allocation function's complexity is as stated. %Payments can be easily computed in time $O(\text{poly}(n, d))$ as in prior work. \junk{ Using Singer's characterization of the threshold payments \cite{singer-mechanisms}, one can verify that they can be computed in time $O(\text{poly}(n, d))$. } \end{proof} Finally, we prove the approximation ratio of the mechanism. We use the following lemma from \cite{chen} which bounds $OPT$ in terms of the value of $S_G$, as computed in Algorithm \ref{mechanism}, and $i^*$, the element of maximum value. \begin{lemma}[\cite{chen}]\label{lemma:greedy-bound} Let $S_G$ be the set computed in Algorithm \ref{mechanism} and let $i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$. We have: \begin{displaymath} OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big). \end{displaymath} \end{lemma} Using Proposition~\ref{prop:relaxation} and~\ref{lemma:greedy-bound} we can complete the proof of Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if $OPT_{-i}'$, the optimal value of $L$ when $i^*$ is excluded from $\mathcal{N}$, has been computed to a precision $\varepsilon$, then the set $S^*$ allocated by the mechanism is such that: \begin{equation} \label{approxbound} OPT \leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\! + \! \varepsilon . \end{equation} To see this, let $L^*_{-i^*}$ be the true maximum value of $L$ subject to $\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line 3 of Algorithm~\ref{mechanism}, we have $L^*_{-i^*}-\varepsilon\leq OPT_{-i^*}' \leq L^*_{-i^*}+\varepsilon$. If the condition on line 4 of the algorithm holds, then \begin{displaymath} V(i^*) \geq \frac{1}{C}L^*_{-i^*}-\frac{\varepsilon}{C} \geq \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}. \end{displaymath} Indeed, $L^*_{-i^*}\geq OPT_{-i^*}$ as $L$ is a fractional relaxation of $V$. Also, $OPT \leq OPT_{-i^*} + V(i^*)$, hence, \begin{equation}\label{eq:bound1} OPT\leq (1+C)V(i^*) + \varepsilon. \end{equation} If the condition does not hold, by observing that $L^*_{-i^*}\leq L^*_c$ and applying Proposition~\ref{prop:relaxation}, we get \begin{displaymath} V(i^*)\leq \frac{1}{C}L^*_{-i^*} + \frac{\varepsilon}{C} \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}. \end{displaymath} Applying Lemma~\ref{lemma:greedy-bound}, \begin{displaymath} V(i^*) \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G) + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C}. \end{displaymath} Thus, if $C$ is such that $C(e-1) -6e +2 > 0$, \begin{align*} V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}. \end{align*} Finally, using Lemma~\ref{lemma:greedy-bound} again, we get \begin{equation}\label{eq:bound2} OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2}\right) V(S_G) + \frac{2e\varepsilon}{C(e-1)- 6e + 2}. \end{equation} To minimize the coefficients of $V_{i^*}$ and $V(S_G)$ in \eqref{eq:bound1} and \eqref{eq:bound2} respectively, we wish to chose $C$ that minimizes \begin{displaymath} \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2} \right)\right). \end{displaymath} This function has two minima, only one of those is such that $C(e-1) -6e +2 \geq 0$. This minimum is \begin{equation}\label{eq:constant} C = \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}. \end{equation} For this minimum, $\frac{2e\varepsilon}{C^*(e-1)- 6e + 2}\leq \varepsilon.$ 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}} 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]$ and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must be in the set selected by the mechanism, otherwise the ratio is unbounded, a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity it remains in the solution; by threshold payment, it is paid at least $B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility and individual rationality: hence, the selected set attains a value $\log2$, while the optimal value is $2\log 2$.\hspace*{\stretch{1}}\qed