\subsection{D-Optimality Criterion}
Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes \eqref{dcrit} within a good approximation ratio. As \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation we consider  the (equivalent) maximization of $V(S) = f(\det\T{X_S}X_S )$, for some strictly increasing, on-to function $f:\reals_+\to\reals_+$. However, the following lower bound implies that such an optimization goal cannot be attained under the costraints of  truthfulness, budget feasibility, and individional rationallity.

\begin{lemma}
For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individionally rational mechanism for budget feasible experiment design with value fuction $V(S) = \det{\T{X_S}X_S}$.
\end{lemma}
\begin{proof}
\input{proof_of_lower_bound1}
\end{proof}

This negative result motivates us to study the following modified objective:
\begin{align}V(S) = \log\det(I_d+\T{X_S}X_S), \label{modified}\end{align} where $I_d\in \reals^{d\times d}$ is the identity matrix.
One possible interpretation of \eqref{modified} is that, prior to the auction, the experimenter has free access to $d$ experiments whose features form an ortho-normal basis in $\reals^d$. However, \eqref{modified} can also be motivated in the context of \emph{Bayesian experimental design} \cite{chaloner1995bayesian}. In short, the objective \eqref{modified} arises naturally when the experimenter retrieves the model $\beta$ through \emph{ridge regression}, rather than the linear regression \eqref{leastsquares} over the observed data; we explore this connection in Section~\ref{sec:bed}. From a practical standpoint, \eqref{modified} is a good approximation of \eqref{dcrit} when the number of experiments is large. Crucially, \eqref{modified} is submodular and satifies $V(\emptyset) = 0$, allowing us to use the extensive machinery for the optimization of submodular functions, as well as recent results in the context of budget feasible auctions. 

\subsection{Truthful, Constant Approximation Mechanism}

In this section we present a mechanism for \EDP. Previous works on maximizing
submodular functions \cite{nemhauser, sviridenko-submodular} and designing
auction mechanisms for submodular utility functions \cite{singer-mechanisms,
chen, singer-influence} rely on a greedy heuristic. In this heuristic, elements
are added to the solution set according to the following greedy selection rule:
assume that you have already selected a set $S$, then the next element to be
included in the solution set is:
\begin{displaymath}
    i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}
\end{displaymath}
This is the generalization of the \emph{value-per-cost} ratio used in greedy
heuristic for knapsack  problems. However, note that for general submodular
functions, the value of an element depends on the set to which it is added.

Unfortunately, even for the non-strategic case, the greedy heuristic gives an
unbounded approximation ratio. Let us introduce $i^*
= \argmax_{i\in\mathcal{N}} V(i)$, the element of maximum value (as a singleton
set). It has been noted by Khuller et al. \cite{khuller} that for the maximum
coverage problem, taking the maximum between the greedy solution and $V(i^*$)
gives a $\frac{2e}{e-1}$ approximation ratio. In the general case, we have the
following result from Singer \cite{singer-influence} which follows from
Chen et al. \cite{chen}:

\begin{lemma}[Singer \cite{singer-influence}]\label{lemma:greedy-bound}
Let $S_G$ be the set computed by the greedy heuristic and let us define $i^*$:
\begin{displaymath}
    i^* = \argmax_{i\in\mathcal{N}} V(i)
\end{displaymath}
then the following inequality holds:
\begin{displaymath}
OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big)
\end{displaymath}
\end{lemma}

Hence, taking the maximum between $V(S_G)$ and $V(i^*)$ yields an approximation
ratio of $\frac{5e}{e-1}$. However, Singer \cite{singer-influence} notes that
this approach breaks incentive compatibility and therefore cannot be directly
applied to the strategic case. Indeed, assume that we are in a situation where
the mechanism has allocated to the greedy set ($V(S_G) \geq V(i^*)$). If an
agent $i$ from the greedy set reduces her cost, it could happen that $V(S_G)$
becomes smaller than $V(i^*)$. In this case the mechanism will allocate to
$i^*$ and $i$ will be out of the allocated set. This breaks the monotonicity of
the allocation function.

The way this issue has been addressed thus far \cite{chen, singer-influence},
is to introduce a third quantity: if $V(i^*)$ is larger than this quantity, the
mechanism allocates to $i^*$, otherwise it allocates to the greedy set $S_G$.
This quantity must be provably close to $V(S_G)$, to keep a bounded
approximation ratio, while maintaining the monotonicity of the allocation
algorithm. Furthermore, it must be computable in polynomial time to keep an
overall polynomial complexity for the allocation algorithm. If the underlying
non-strategic optimization program \eqref{eq:non-strategic} can be solved in
polynomial time, Chen et al. \cite{chen} prove that allocating to $i^*$ when
$V(i^*) \geq C\cdot OPT(V,\mathcal{N}\setminus\{i^*\}$ (for some constant $C$)
and to $S_G$ otherwise yields a 8.34 approximation mechanism. For specific
problems, Chen et al. \cite{chen} for knapsack on one hand, Singer
\cite{singer-influence} for maximum coverage on the other hand, instead compare
$V(i^*)$ to $OPT(R_{\mathcal{N}\setminus\{i\}}, B)$, where $R_\mathcal{N}$
denotes a fractional relaxation of the function $V$ over the set $\mathcal{N}$.

We say that $R_\mathcal{N}$ is a fractional relaxation of $V$ over the set
$\mathcal{N}$, if (a) $R_\mathcal{N}$ is a function defined on the hypercube
$[0, 1]^{|\mathcal{N}|}$ and (b) for all $S\subseteq\mathcal{N}$, if
$\mathbf{1}_S$ denotes the indicator vector of $S$ we have
$R_\mathcal{N}(\mathbf{1}_S) = V(S)$. A relaxation which is commonly used, due
to its well-behaved properties in the context of maximizing submodular
functions, is the \emph{multi-linear} extension:
\begin{equation}\label{eq:multilinear}
    F_\mathcal{N}^V(\lambda) 
    = \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[V(S)\right]
    = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)
\end{equation}
$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if
we decide for each element in $\mathcal{N}$ to pick it with probability
$\lambda_i$ or to reject it with probability $1-\lambda_i$:
\begin{displaymath}
    P_\mathcal{N}^\lambda(S) = \prod_{i\in S} \lambda_i
    \prod_{i\in\mathcal{N}\setminus S} 1 - \lambda_i
\end{displaymath}
For knapsack, Chen et al. \cite{chen} directly use the multi-linear extension as
the relaxation to compare $V(i^*)$ to. For maximum coverage however, the
optimal value of the multi-linear extension cannot be computed in polynomial
time. Thus, Singer \cite{singer-influence} introduces a second relaxation of
the value function which can be proven to be close to the multi-linear
extension, by using the \emph{pipage rounding} method from Ageev and Sviridenko
\cite{pipage}.

Here, following these ideas, we introduce another relaxation of the value
function. Note that in our case, the multi-linear extension can be written:
\begin{displaymath}
    F_\mathcal{N}(\lambda) = \mathbb{E}_{S\sim
    P_\mathcal{N}^\lambda}\left[\log\det A(S) \right]
    \;\text{with}\; A(S) = I_d + \sum_{i\in S} x_i\T{x_i}
\end{displaymath}
Our relaxation follows naturally by swapping the expectation and the $\log\det$
in the above formula:
\begin{align}\label{eq:concave}
    L_\mathcal{N}(\lambda) & \defeq \log\det\left(\mathbb{E}_{S\sim
    P_\mathcal{N}^\lambda}[A(S)]\right)\notag \\
    &= \log\det\left(I_d + \sum_{i\in\mathcal{N}}
    \lambda_i x_i\T{x_i}\right)
\end{align}
This function is well-known to be concave (see \emph{e.g.}
\cite{boyd2004convex}). Hence, its maximum value can be computed in polynomial
time (TODO elaborate) and can be used as a threshold rule in our mechanism.
The main challenge will be to prove that $OPT(L_\mathcal{N}, B)$ is close to
$V(S_G)$. To do so, our main technical contribution is to prove that
$L_\mathcal{N}$ has a bounded approximation ratio to the value function $V$
(lemma~\ref{lemma:relaxation}).

The mechanism for \EDP{} is presented in algorithm \ref{mechanism}.
\begin{algorithm}
    \caption{Mechanism for \EDP{}}\label{mechanism}
    \begin{algorithmic}[1]
    \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
    \State $x^* \gets \argmax_{x\in[0,1]^{|\mathcal{N}|}} \{L_{\mathcal{N}\setminus\{i^*\}}(x)
                                    \mid c(x)\leq B\}$
        \Statex
        \If{$L(x^*) < CV(i^*)$}
            \State \textbf{return} $\{i^*\}$
        \Else
            \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
            \State $S_G \gets \emptyset$
            \While{$c_i\leq \frac{B}{2}\frac{V(S_G\cup\{i\})-V(S_G)}{V(S_G\cup\{i\})}$}
                \State $S_G \gets S_G\cup\{i\}$
                \State $i \gets \argmax_{j\in\mathcal{N}\setminus S_G}
                \frac{V(S_G\cup\{j\})-V(S_G)}{c_j}$
            \EndWhile
            \State \textbf{return} $S_G$
        \EndIf
    \end{algorithmic}
\end{algorithm}

We can now state the main result of this section:
\begin{theorem}\label{thm:main}
    The mechanism described in Algorithm~\ref{mechanism} is truthful,
    and budget feasible. Furthermore, choosing:
    \begin{displaymath}
        C = C^* =  \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)}
    \end{displaymath}
    we get an approximation ratio of:
    \begin{displaymath}
        1 + C^* = \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)}\simeq 19.68
    \end{displaymath}
\end{theorem}

\stratis{Add lowerbound here too.}

\subsection{Proof of theorem~\ref{thm:main}}

\stratis{Explain what are the main steps in the proof}
\begin{lemma}\label{lemma:monotone}
The mechanism is monotone.
\end{lemma}

\begin{proof}
    Suppose, for contradiction, that there exists a user $i$ that has been
    selected by the mechanism and that would not be selected had he reported
    a cost $c_i'\leq c_i$ (all the other costs staying the same).

    If $i\neq i^*$ and $i$ has been selected, then we are in the case where
    $L_\mathcal{N}(x^*) \geq C V(i^*)$ and $i$ was included in the result set by the greedy
    part of the mechanism. By reporting a cost $c_i'\leq c_i$, 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. Let us 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$. Moreover:
    \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*}
    Hence $i$ will still be included in the result set.

    If $i = i^*$, $i$ is included iff $L_\mathcal{N}(x^*) \leq C V(i^*)$. Reporting $c_i'$
    instead of $c_i$ does not change the value $V(i^*)$ nor $L_\mathcal{N}(x^*)$ (which is
    computed over $\mathcal{N}\setminus\{i^*\}$). Thus $i$ is still included by
    reporting a different cost.
\end{proof}

\begin{lemma}\label{lemma:budget-feasibility}
The mechanism is budget feasible.
\end{lemma}

\begin{proof}
Let us denote by $S_G$ the set selected by the greedy heuristic in the
mechanism of Algorithm~\ref{mechanism}. Let $i\in S_G$, let us also denote by
$S_i$ the solution set that was selected by the greedy heuristic before $i$ was
added. Recall from \cite{chen} that the following holds for any submodular
function: if the point $i$ was selected by the greedy heuristic, then:
\begin{equation}\label{eq:budget}
    c_i \leq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B
\end{equation}

\stratis{Use ``recall'' only for  something the reader is likely to know. }

Assume now that our mechanism selects point $i^*$. In this case, his payment
his $B$ and the mechanism is budget-feasible.

Otherwise, the mechanism selects the set $S_G$. In this case, \eqref{eq:budget}
shows that the threshold payment of user $i$ is bounded by:
\begin{displaymath}
\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B
\end{displaymath}

Hence, the total payment is bounded by:
\begin{displaymath}
    \sum_{i\in S_M} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B \leq B
\end{displaymath}
\end{proof}

\begin{lemma}\label{lemma:approx}
    Let $S^*$ be the set allocated by the mechanism. Let us write:
    \begin{displaymath}
        C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C
        (e-1) -10e  +2}\right)\right)
    \end{displaymath}

    Then:
    \begin{displaymath}
        OPT(V, \mathcal{N}, B) \leq
        C_\text{max}\cdot V(S^*) 
    \end{displaymath}
\end{lemma}

\begin{proof}

    If the condition on line 3 of the algorithm holds, then:
    \begin{displaymath}
        V(i^*) \geq \frac{1}{C}L(x^*) \geq
        \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B)
    \end{displaymath}

    But:
    \begin{displaymath}
        OPT(V,\mathcal{N},B) \leq OPT(V,\mathcal{N}\setminus\{i\}, B) + V(i^*)
    \end{displaymath}

    Hence:
    \begin{displaymath}
        V(i^*) \geq \frac{1}{C+1} OPT(V,\mathcal{N}, B)
    \end{displaymath}

    If the condition of the algorithm does not hold, by applying lemmas
    \ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
    \begin{align*}
        V(i^*) & \leq \frac{1}{C}L(x^*) \leq \frac{1}{C}
        \big(4 OPT(V,\mathcal{N}, B) + 2 V(i^*)\big)\\
        & \leq \frac{1}{C}\left(\frac{4e}{e-1}\big(3 V(S_G)
        + 2 V(i^*)\big)
        + V(i^*)\right)
    \end{align*}
    
    Thus:
    \begin{align*}
        V(i^*) \leq \frac{12e}{C(e-1)- 10e + 2} V(S_G)
    \end{align*}

    Finally, using again lemma~\ref{lemma:greedy-bound}, we get:
    \begin{displaymath}
        OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{8e}{C
        (e-1) -10e  +2}\right) V(S_G)\qed
    \end{displaymath}
\end{proof}

The optimal value for $C$ is:
\begin{displaymath}
    C^* = \argmin_C C_{\textrm{max}}
\end{displaymath}

This equation has two solutions. Only one of those is such that:
\begin{displaymath}
    C(e-1) -10e  +2 \geq 0
\end{displaymath}
which is needed in the proof of the previous lemma. Computing this solution,
gives the result of the theorem.

\subsection{An approximation ratio for $L_\mathcal{N}$}\label{sec:relaxation}

Our main contribution is lemma~\ref{lemma:relaxation} which gives an
approximation ratio for $L_\mathcal{N}$ and is key in the proof of
theorem~\ref{thm:main}.

It has been observed already (see for example \cite{dughmi}) that the
multi-linear extension presents the cross-convexity property: it is convex along
any direction $e_i-e_j$ where $e_i$ and $e_j$ are two elements of the standard
basis. This property allows to trade between two fractional components of
a point without diminishing the value of the relaxation. The following lemma
follows is inspired by a similar lemma from \cite{dughmi} but also ensures that
the points remain feasible during the trade. 

\stratis{explain how the proof below relates to the $\epsilon$-convexity of sviridenko}
\begin{lemma}[Rounding]\label{lemma:rounding}
    For any feasible $\lambda\in[0,1]^{|\mathcal{N}|}$, there exists a feasible
    $\bar{\lambda}\in[0,1]^{|\mathcal{N}|}$ such that at most one of its component is
    fractional, that is, lies in $(0,1)$ and:
    \begin{displaymath}
        F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})
    \end{displaymath}
\end{lemma}

\begin{proof}
    We give a rounding procedure which given a feasible $\lambda$ with at least
    two fractional components, returns some $\lambda'$ with one less fractional
    component, feasible such that:
    \begin{displaymath}
        F_\mathcal{N}(\lambda) \leq F_\mathcal{N}(\lambda')
    \end{displaymath}
    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{multline}\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{multline}

    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{multline*}
        \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{multline*}
    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}

\begin{lemma}\label{lemma:relaxation-ratio}
    The following inequality holds:
    \begin{displaymath}
        \forall\lambda\in[0,1]^{|\mathcal{N}|},\; 
        \frac{1}{2}
        \,L_\mathcal{N}(\lambda)\leq
        F_\mathcal{N}(\lambda)\leq L_{\mathcal{N}}(\lambda)
    \end{displaymath}
\end{lemma}

\begin{proof}

    We will prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i
    F_\mathcal{N}(\lambda)/\partial_i L_\mathcal{N}(\lambda)$.

    \stratis{what is $\partial_i?$}. 

    This will be enough to conclude, by observing that:
    \begin{displaymath}
        \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}
        \sim_{\lambda\rightarrow 0}
        \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F_\mathcal{N}(0)}
        {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L_\mathcal{N}(0)}
    \end{displaymath}
    \stratis{what about other boundaries?}
   and that an interior critical point of the ratio
    $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$ is characterized by:
    \begin{displaymath}
        \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}
        = \frac{\partial_i F_\mathcal{N}(\lambda)}{\partial_i
        L_\mathcal{N}(\lambda)}
    \end{displaymath}


    Let us start by computing the derivatives of $F_\mathcal{N}$ and
    $L_\mathcal{N}$ with respect to
    the $i$-th component.

    For $F$, it suffices to look at the derivative of
    $P_\mathcal{N}^\lambda(S)$:
    \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{multline*}
        \partial_i F_\mathcal{N} =
        \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{multline*}

    Now, using that every $S$ such that $i\in S$ can be uniquely written as
    $S'\cup\{i\}$, we can write:
    \begin{multline*}
        \partial_i F_\mathcal{N} =
        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S\cup\{i\})\\
        - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)\\
    \end{multline*}

    Finally, by using the expression for the marginal contribution of $i$ to
    $S$:
    \begin{displaymath}
        \partial_i F_\mathcal{N}(\lambda) = 
        \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_\mathcal{N}$ uses standard matrix
    calculus and gives:
    \begin{displaymath}
        \partial_i L_\mathcal{N}(\lambda)
        = \T{x_i}\tilde{A}(\lambda)^{-1}x_i
    \end{displaymath}
    
    Using the following inequalities:
    \begin{gather*}
        \forall S\subseteq\mathcal{N}\setminus\{i\},\quad
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq
        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})\\
        \forall S\subseteq\mathcal{N},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S) 
        \geq P_\mathcal{N}^\lambda(S)\\
        \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \geq A(S\cup\{i\})^{-1}\\
    \end{gather*}
    we get:
    \begin{align*}
        \partial_i F_\mathcal{N}(\lambda) 
        & \geq \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}{2}
        \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)\\
        &\hspace{-3.5em}+\frac{1}{2}
        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
        P_\mathcal{N}^\lambda(S\cup\{i\})
        \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\
        &\geq \frac{1}{2}
        \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)\geq I_d$ we get that:
    \begin{displaymath}
        \T{x_i}A(S)^{-1}x_i \leq 1 
    \end{displaymath}
    
    Moreover:
    \begin{displaymath}
        \forall x\leq 1,\; \log(1+x)\geq x
    \end{displaymath}

    Hence:
    \begin{displaymath}
        \partial_i F_\mathcal{N}(\lambda) \geq
        \frac{1}{2}
        \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{align*}
        \partial_i F_\mathcal{N}(\lambda) &\geq
        \frac{1}{2}
        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i\\
        & \geq \frac{1}{2}
        \partial_i L_\mathcal{N}(\lambda)\qed
    \end{align*}
\end{proof}

\begin{lemma}\label{lemma:relaxation}
    We have:
    \begin{displaymath}
        OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B)
        + 2\max_{i\in\mathcal{N}}V(i)
    \end{displaymath}
\end{lemma}

\begin{proof}
    Let us consider a feasible point $\lambda^*\in[0,1]^{|\mathcal{N}|}$ such that $L_\mathcal{N}(\lambda^*)
    = OPT(L_\mathcal{N}, B)$. 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_\mathcal{N}(\lambda^*) \leq 2
        F_\mathcal{N}(\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$.
    Using the fact that $F_\mathcal{N}$ is linear with respect to the $i$-th
    component and is a relaxation of the value function, we get:
    \begin{displaymath}
        F_\mathcal{N}(\bar{\lambda}) = V(S) +\lambda_i V(S\cup\{i\})
    \end{displaymath}

    Using the submodularity of $V$:
    \begin{displaymath}
        F_\mathcal{N}(\bar{\lambda}) \leq 2 V(S) + V(i)
    \end{displaymath}

    Note that since $\bar{\lambda}$ is feasible, $S$ is also feasible and
    $V(S)\leq OPT(V,\mathcal{N}, B)$. Hence:
    \begin{equation}\label{eq:e2}
        F_\mathcal{N}(\bar{\lambda}) \leq 2 OPT(V,\mathcal{N}, B)
        + \max_{i\in\mathcal{N}} V(i)
    \end{equation}

    Putting \eqref{eq:e1} and \eqref{eq:e2} together gives the results.
\end{proof}