path: root/main.tex

\label{sec:main}
%\subsection{Truthful, Constant Approximation Mechanism}

In this section we present a mechanism for \EDP.

\paragraph{Prior approach to submodular optimization problems} 
 Previous works~\cite{nemhauser, sviridenko-submodular,singer-mechanisms,chen, singer-influence}
%
%on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and designing
%auction mechanisms for submodular value functions \cite{singer-mechanisms,
%chen, singer-influence} 
%
rely on a greedy algorithm. In this algorithm, elements
are added to the solution set according to the following greedy selection rule.
Assume that $S\subseteq \mathcal{N}$ is the solution set constructed thus far; then, the next element $i$ to be
included in $S$ is the one with the highest \emph{marginal-value-per-cost}:
\begin{align}
    i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy}
\end{align}
This process terminates when no more items can be added to $S$ using \eqref{greedy} under budget $B$. This is the generalization of the \emph{value-per-cost} ratio used in the greedy approximation
algorithm for \textsc{Knapsack}. However, in contrast to \textsc{Knapsack}, for general submodular
functions, the marginal value  of an element in \eqref{greedy} depends on the set to which the element is added.
Similarly, the value of an element depends on the set in which it is
considered. 
%However, in the following, the value of an element $i$ will refer to
%its value as a singleton set: $V(\{i\})$. If there is no ambiguity, we will write
%$V(i)$ instead of $V(\{i\})$.
Unfortunately, even for the full information case, the greedy algorithm gives an
unbounded approximation ratio. Instead, 
\junk{
 Let  $i^*
= \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value.
% (as a singleton set).
%It has been noted by Khuller \emph{et al.}~\cite{khuller} that 
For the maximum
coverage problem, taking the maximum between the greedy solution and $V(i^*)$ (shorthand for $V(\{i\})$)
gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller}. In the general sub modular case, 
\junk{we have the
following result from Singer \cite{singer-influence} which follows from
Chen \emph{et al.}~\cite{chen}: \stratis{Is it Singer or Chen? Also, we need to introduce $V(i)$ somewhere...}
}
}
\begin{lemma}~\cite{chen}\label{lemma:greedy-bound}
Let $S_G$ be the set computed by the greedy algorithm and let 
%define $i^*$:
%\begin{displaymath}
$i^* = \argmax_{i\in\mathcal{N}} V(i).$
%\end{displaymath}
We have:
% the following inequality holds:
\begin{displaymath}
OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
\end{displaymath}
\end{lemma}
Thus, 
taking the maximum between $V(S_G)$ and $V(i^*)$ yields an approximation
ratio of $\frac{5e}{e-1}$.  However, 
this approach breaks incentive compatibility and therefore cannot be directly
applied to the strategic case~\cite{singer-influence}.
\junk{
Indeed, suppose this allocation mechanism is used, and consider a case where
the allocates  the greedy set ($V(S_G) \geq V(i^*)$). If an
agent $i$ from $S_G$ reduces her cost, it could happen that $V(S_G)$
becomes smaller than $V(i^*)$. In this case the mechanism's allocation becomes
$i^*$, and $i$ is excluded from the allocated set. This violates the monotonicity of
the allocation function and hence also truthfulness, by Myerson's Theorem.
}

For the strategic case, 
\begin{itemize}
\item
When the underlying
full information problem \eqref{eq:non-strategic} can be solved in
polynomial time, Chen \emph{et al.}~\cite{chen} prove that  
%$OPT_{-i^*}$, the optimal solution to \eqref{eq:non-strategic} when $i^*$ is excluded from set $\mathcal{N}$, can play the %role of this quantity: that is, 
allocating to $i^*$ when
$V(i^*) \geq C\cdot OPT_{-i^*}$ (for some constant $C$)
and to $S_G$ otherwise yields a 8.34-approximation mechanism. However, this is not a poly-time mechanism when the underlying problem is NP hard (unless P=NP), as is the case for \EDP.

\item
For  NP-hard 
problems, consider 
the optimal value of a \emph{fractional relaxation} of the function $V$ over the set
$\mathcal{N}$. A function $R:[0, 1]^{n}\to\reals_+$ defined on the hypercube  $[0, 1]^{n}$ is a fractional relaxation of $V$
over the set $\mathcal{N}$ if %(a) $R$ is a function defined on the hypercube $[0, 1]^{n}$ and (b) 
  $R(\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' = \argmax_{\lambda\in[0, 1]^{n}}
    \left\{R(\lambda) \mid \sum_{i=1}^{n} \lambda_i c_i
    \leq B\right\}\label{relax}
\end{align}
Substituting $OPT'_{-i^*}$ for $OPT_{-i^*}$ like before works for specific problems like \textsc{Knapsack}~\cite{chen} and 
\textsc{Coverage}~\cite{singer-influence}. For other instances of sub modular function, this overall technology
has to be applied and extended.
\end{itemize}


\junk{
To address this, Chen \emph{et al.}~\cite{chen} %and Singer~\cite{singer-influence},
 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. 

\sloppy
When the underlying
full information problem \eqref{eq:non-strategic} can be solved in
polynomial time, Chen et al. \cite{chen} prove that  $OPT_{-i^*}$, the optimal solution to \eqref{eq:non-strategic} when $i^*$ is excluded from set $\mathcal{N}$, can play the role of this quantity: that is, allocating to $i^*$ when
$V(i^*) \geq C\cdot OPT_{-i^*}$ (for some constant $C$)
and to $S_G$ otherwise yields a 8.34-approximation mechanism. However, this is not a poly-time mechanism when the underlying problem is NP hard (unless P=NP), as is the case for \EDP.


\fussy
For  NP-hard 
problems, Chen et al.~\cite{chen} %for \textsc{Knapsack} and Singer
%\cite{singer-influence} for \textsc{Coverage} instead 
propose comparing
$V(i^*)$ to %$OPT(R_{\mathcal{N}\setminus\{i\}}, B)$, where $R$ denotes 
the optimal value of a \emph{fractional relaxation} of the function $V$ over the set
$\mathcal{N}$. A function $R:[0, 1]^{n}\to\reals_+$ defined on the hypercube  $[0, 1]^{n}$ is a fractional relaxation of $V$
over the set $\mathcal{N}$ if %(a) $R$ is a function defined on the hypercube $[0, 1]^{n}$ and (b) 
  $R(\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' = \argmax_{\lambda\in[0, 1]^{n}}
    \left\{R(\lambda) \mid \sum_{i=1}^{n} \lambda_i c_i
    \leq B\right\}\label{relax}
\end{align}
To attain truthful constant approximation mechanism for \textsc{Knapsack},  Chen \emph{et al.}~\cite{chen}  substitute $OPT'_{-i^*}$ for $OPT_{-i^*}$ in the above program, where $R$ is a relaxation of the \textsc{Knapsack} objective.
Similarly, Singer~\cite{singer-influence} follows the same approach to obtain a mechanism for \textsc{Coverage}.
}

\paragraph{Our approach}
We build on~\cite{chen,singer-influence}. 
We introduce a relaxation specifically tailored to the value
function of \EDP.
$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if
we select each element $i$ in $\mathcal{N}$  independently 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}
Consider  the general \emph{multi-linear}
extension:
\begin{equation}\label{eq:multilinear}
    F(\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}
\junk{

$P_\mathcal{N}^\lambda(S)$ is the probability of choosing the set $S$ if
we select each element $i$ in $\mathcal{N}$  independently 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 \textsc{Knapsack}, Chen et al. \cite{chen} directly use the multi-linear extension, as in this case \eqref{relax} can be solved in polynomial time. % for the \textsc{Knapsack} objective.
 For \textsc{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. The latter is proved to be close to the multi-linear
extension using the \emph{pipage rounding} method of Ageev and Sviridenko
\cite{pipage}.

Here, following these ideas, we introduce a relaxation specifically tailored to the value
function of \EDP. 
}
For \EDP\  the multi-linear extension 
%of \eqref{modified} 
can be written:
\begin{displaymath}
    F(\lambda) = \mathbb{E}_{S\sim
    P_\mathcal{N}^\lambda}\Big[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big].
\end{displaymath}
%As in the case of \textsc{Coverage}, 
\eqref{relax} is not a convex optimization problem, and is not easy to solve directly. %As in ~\cite{singer-influence},
We consider an additional relaxation $L$ that 
follows naturally by swapping the expectation and the $\log\det$
in the above formula:
\begin{align}\label{eq:concave}
    L(\lambda) & \defeq \log\det\Big(\mathbb{E}_{S\sim
    P_\mathcal{N}^\lambda}\big[I_d + \sum_{i\in S} x_i\T{x_i}\big]\Big)\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 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 it is possible
to find the maximum of $L$ to any precision $\varepsilon$ in
a number of iterations $O(\log\log\varepsilon^{-1})$. 
The main challenge will
be to prove that $OPT'$ in~\eqref{relax}, for the relaxation $R=L$, is close to $V(S_G)$, which we will address later and is the technical
bulk of the 
paper. 
\junk{
To do so, our
main technical contribution is to prove that $L$ has a bounded
approximation ratio to the value function $V$ (Lemma~\ref{lemma:relaxation}).
}

\begin{algorithm}[!t]
    \caption{Mechanism for \EDP{}}\label{mechanism}
    \begin{algorithmic}[1]
    \State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$
    \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
    \State $\xi \gets \argmax_{\lambda\in[0,1]^{n}} \{L(\lambda)
                                    \mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$
        \Statex
        \If{$L(\xi) < C \cdot V(i^*)$} \label{c}
            \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}

The resulting mechanism for \EDP{} is composed of
\begin{itemize}
\item
 the allocation function
presented in Algorithm~\ref{mechanism}, and 
\item
the payment function which pays each
allocated agent $i$ her threshold payment as described in Myerson's Theorem. 
%The constant $C$ is an absolute
%constant that determined in Section~\ref{sec:proofofmainthm}
%(see \eqref{eq:c}). 
 In the case where
$\{i^*\}$ is the allocated set, her threshold payment is $B$ (she would be have
been dropped on line 1 of Algorithm~\ref{mechanism} had she reported a higher
cost). In the case where $S_G$ is the allocated set, threshold payments'
characterization from~\cite{singer-mechanisms} gives a formula to
 compute these payments.
 \end{itemize}

We can now state our main result:
\begin{theorem}\label{thm:main}
    \sloppy
    The allocation described in Algorithm~\ref{mechanism}, along with threshold payments, is truthful, individually rational 
    and budget feasible. Furthermore, for any $\varepsilon>0$, the mechanism
  runs in time  $O\left(\text{poly}(n, d,
    \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that:
    \begin{align*}
        OPT
        & \leq \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)} V(S^*)+
        \varepsilon\\
        & \simeq 19.68V(S^*) + \varepsilon
    \end{align*}
\end{theorem}

\fussy

%\stratis{Add lowerbound here too.}
%Note that this implies we construct a poly-time mechanism with accuracy arbitrarily close to 19.68, by taking $\varepsilon = \ldots$\stratis{fix me}.
In addition, we prove the following simple lower bound.
\begin{theorem}\label{thm:lowerbound}
There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. 
\end{theorem}
%\stratis{move the proof as appropriate}
\begin{proof}
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$.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
%\stratis{individual rationality???}
%The proof of the properties of the mechanism is broken down into lemmas.

We now present the proof of Theorem~\ref{thm:main}. Truthfulness and individual
rationality follows from monotonicity and threshold payments.  Monotonicity and
budget feasibility follow more or less from the analysis of Chen \emph{et al.} \cite{chen};
we briefly restate the proofs below for the sake of completeness.
 Our proof of the approximation ratio uses a bound on our concave relaxation
$L$ (Lemma~\ref{lemma:relaxation}). This is our main technical
contribution; the proof of this lemma can be found in Section~\ref{sec:relaxation}.
\begin{lemma}\label{lemma:monotone}
The mechanism is monotone.
\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$ while all  other costs stay the same.
    Suppose that when $i$ reports $c_i$, $L(\xi) \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$.
     By reporting a cost $c_i'\leq 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'$. As $L(\xi)$,  is the optimal value of \eqref{relax} under relaxation $L$ when $i^*$ is excluded from $\mathcal{N}$, reducing the costs can only increase this value, so under $c'_i\leq c_i$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$.
    Suppose now that when $i$ reports $c_i$, $L(\xi) < 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
    $L(\xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$. 
\end{proof}
\begin{lemma}\label{lemma:budget-feasibility}
The mechanism is budget feasible.
\end{lemma}
\begin{proof}
Suppose that $L(\xi) < 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 $L(\xi) \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}

\begin{lemma}\label{lemma:complexity}
    For any $\varepsilon > 0$, the complexity of the mechanism  is
    $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$.
\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$. 
    The function $\log\det$ is concave and self-concordant (see
    \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be find
    to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$  of iterations of Newton's method. Each iteration  can be
    done in time $O(\text{poly}(n, d))$. Thus, 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  which establishes that $OPT'$, the optimal value \eqref{relax} of the fractional relaxation $L$ under the budget constraints
 is not too far from $OPT$.  
\begin{lemma}\label{lemma:relaxation}
    %\begin{displaymath}
     $   OPT' \leq 4 OPT
        + 2\max_{i\in\mathcal{N}}V(i)$
    %\end{displaymath}
\end{lemma}
The proof of Lemma~\ref{lemma:relaxation} is our main technical contribution, and can be found in Section \ref{sec:relaxation}.

\paragraph{Finishing Proof of Theorem~\ref{thm:main} }
Note that the lower bound $OPT' \geq  OPT
$ also holds trivially, as $L$ is a fractional relaxation of $V$ over $\mathcal{N}$.
Using Lemma~\ref{lemma:relaxation} we can complete the proof of Theorem~\ref{thm:main} by showing that, %\begin{lemma}\label{lemma:approx}
    %C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C
    %(e-1) -10e  +2}\right)\right)
    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{align}
        OPT
         \leq \frac{14e\!-\!3 + \sqrt{160e^2\!-\!48e\!+\!9}}{2(e\!-\!1)} V(S^*)\!+\! \varepsilon \label{approxbound}
    \end{align}
%\end{lemma}
    To see this, let $OPT_{-i^*}'$ be the true maximum value of $L$ subject to $\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. Assume that on line 3 of algorithm~\ref{mechanism}, a quantity
    $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq OPT_{-i^*}' \leq
    \tilde{L}+\varepsilon$ has been computed (Lemma~\ref{lemma:complexity}
    states that this  is computed in time within our complexity guarantee).
    If the condition on line 3 of the algorithm holds, then:
    \begin{displaymath}
        V(i^*) \geq \frac{1}{C}OPT_{-i^*}'-\frac{\varepsilon}{C} \geq
        \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C} 
    \end{displaymath}
    as $L$ is a fractional relaxation of $V$.  Also,
    \begin{displaymath}
        OPT \leq OPT_{-i^*} + V(i^*)
    \end{displaymath}
    Hence:
    \begin{equation}\label{eq:bound1}
        OPT\leq (1+C)V(i^*) + \varepsilon
    \end{equation}
    Note that $OPT_{-i^*}'\leq OPT'$. If the condition  does not hold, 
    from Lemmas \ref{lemma:relaxation} and \ref{lemma:greedy-bound}:
    \begin{align*}
        V(i^*) & \stackrel{}\leq \frac{1}{C}OPT_{-i^*}'+ \frac{\varepsilon}{C}\leq \frac{1}{C}
        \big(4 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}\\
        & \leq \frac{1}{C}\left(\frac{4e}{e-1}\big(3 V(S_G)
        + 2 V(i^*)\big)
        + 2 V(i^*)\right) + \frac{\varepsilon}{C}
    \end{align*}
    Thus, if $C$ is such that $C(e-1) -10e  +2 > 0$,
    \begin{align*}
        V(i^*) \leq \frac{12e}{C(e-1)- 10e + 2} V(S_G) 
        + \frac{(e-1)\varepsilon}{C(e-1)- 10e + 2}
    \end{align*}
    Finally, using again Lemma~\ref{lemma:greedy-bound}, we get:
    \begin{multline}\label{eq:bound2}
        OPT(V, \mathcal{N}, B) \leq \frac{3e}{e-1}\left( 1 + \frac{8e}{C
        (e-1) -10e  +2}\right) V(S_G)\\
        +\frac{2e\varepsilon}{C(e-1)- 10e + 2}
    \end{multline}
    To minimize the coefficients of $V_{i^*}$  and $V(S_G)$  in \eqref{eq:bound1} and \eqref{eq:bound2} respectively,
    we wish to chose for $C=C^*$ such that:
    \begin{displaymath}
        C^* = \argmin_C 
        \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C (e-1) -10e  +2}
        \right)\right)
    \end{displaymath}
    This equation has two solutions. Only one of those is such that:
      $  C(e-1) -10e  +2 \geq 0$.
    %which is needed in the above derivation. 
This solution is:
    \begin{align}
        C^* =  \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)} \label{eq:c}
    \end{align}
    For this solution,
 %   \begin{displaymath}
  $      \frac{2e\varepsilon}{C^*(e-1)- 10e + 2}\leq \varepsilon. $
 %   \end{displaymath}
    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
%\end{proof}

\subsection{Proof of Lemma~\ref{lemma:relaxation}}\label{sec:relaxation}
%Recall that, since $L$ is a fractional relaxation of  $V$, 
%\begin{displaymath}
%    OPT \leq OPT(L, B).
%\end{displaymath}
%However, for the purpose of proving theorem~\ref{thm:main}, we need to bound
%$L$ from above (up to a multiplicative factor) by $V$. 

\junk{
To prove Lemma~\ref{lemma:relaxation}, we use the
\emph{pipage rounding} method of Ageev and Sviridenko~\cite{pipage}, where
$L$ is first bounded from above by the multi-linear relaxation $F$, which is itself
subsequently bounded by $V$. While the latter part is general and can be applied
to the multi-linear extension of any submodular function, the former part is
specific to our choice for the function $L$.  %and is our main technical contribution (lemma~\ref{lemma:relaxation-ratio}).

The proof has two aspects. The easier part is that $F$ is bounded by $V$.
This is called  \emph{cross-convexity}  in the literature (see, \emph{e.g.},
\cite{dughmi}), or $\varepsilon$-convexity by Ageev and Sviridenko~\cite{pipage}. 
}

We prove that our multi-linear function $F$ has a property 
 which allows to trade one fractional component of the solution for another until
one of them becomes integral, without losing any value.
This property is referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.},
\cite{dughmi}), or $\varepsilon$-convexity by Ageev and
Sviridenko~\cite{pipage}.
\junk{

a variant of the $\varepsilon$-convexity of the multi-linear
extension \eqref{eq:multilinear} introduced by Ageev and Sviridenko
\cite{pipage} which allows to trade one fractional component of the solution for another until
one of them becomes integral, without loosing any value. This property is also
referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.},
\cite{dughmi}). 
}
Formally, %this property states that 
if we define:
\begin{displaymath}
    \tilde{F}_\lambda(\varepsilon) \defeq F\big(\lambda + \varepsilon(e_i
    - e_j)\big)
\end{displaymath}
where $e_i$ and $e_j$ are two vectors of the standard basis of
$\reals^{n}$, then $\tilde{F}$ is convex. Hence its maximum over the interval:
\begin{displaymath}
 I_\lambda = \Big[\max(-\lambda_i,\lambda_j-1), \min(1-\lambda_i, \lambda_j)\Big]
\end{displaymath}
is attained at one of the boundaries of $I_\lambda$ for which one of the $i$-th
or the $j$-th component of $\lambda$ becomes integral.

The lemma below proves that we can similarly trade a fractional component for
an other until one of them becomes integral \emph{while maintaining the
feasibility of the point at which $F$ is evaluated}. 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$.
\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 
    %\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 feasible $\lambda'$ with one less fractional
    component such that:
    \begin{displaymath}
        F(\lambda) \leq F(\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}

Next, we prove the central result of bounding $L$  appropriately in terms of $F$.

\junk{
To prove Lemma~\ref{lemma:relaxation}, we use the
\emph{pipage rounding} method of Ageev and Sviridenko~\cite{pipage}, where
$L$ is first bounded from above by the multi-linear relaxation $F$, which is itself
subsequently bounded by $V$. While the latter part is general and can be applied
to the multi-linear extension of any submodular function, the former part is
specific to our choice for the function $L$.  %and is our main techn
}

\begin{lemma}\label{lemma:relaxation-ratio}
 %   The following inequality holds:
For all $\lambda\in[0,1]^{n},$
    %\begin{displaymath}
     $           \frac{1}{2}
        \,L(\lambda)\leq
        F(\lambda)\leq L(\lambda)$.
    %\end{displaymath}
\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) =I_d+ \T{X_S}X_S$. 
%  $  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{align*}
        \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{align*}
    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}
    Finally:
    \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. In particular, 
  matrix inversion is decreasing and convex over symmetric
positive definite matrices.
In particular,
\begin{gather*}
        \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}
\end{gather*}
 Observe that:
    \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)
    \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:
    \begin{displaymath}
        \T{x_i}A(S)^{-1}x_i \leq \norm{x_i}_2^2 \leq 1 
    \end{displaymath}
    Moreover:
    \begin{displaymath}
        \forall x\leq 1,\; \log(1+x)\geq x
    \end{displaymath}
    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{align*}
        \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{align*}

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}

\paragraph{Proof of  Lemma~\ref{lemma:relaxation}}
Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*)
    = OPT'$. 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$.
    Using the fact that $F$ is linear with respect to the $i$-th
    component and is a relaxation of the value function, we get:
    \begin{displaymath}
        F(\bar{\lambda}) = V(S) +\lambda_i V(S\cup\{i\})
    \end{displaymath}
    Using the submodularity of $V$:
    \begin{displaymath}
        F(\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$. Hence:
    \begin{equation}\label{eq:e2}
        F(\bar{\lambda}) \leq 2 OPT
        + \max_{i\in\mathcal{N}} V(i)
    \end{equation}
    Together, \eqref{eq:e1} and \eqref{eq:e2} imply the lemma. \hspace*{\stretch{1}}\qed