Unifying pass over the whole paper

1 files changed, 178 insertions, 149 deletions

diff --git a/approximation.tex b/approximation.tex
index ced53ed..926ca1d 100644
--- a/approximation.tex
+++ b/approximation.tex
@@ -1,9 +1,8 @@
-Even though \EDP{} is NP-hard, designing a mechanism for this problem will
-involve being able to find an approximation $\tilde{L}^*(c)$ of $OPT$
-monotonous with respect to coordinate-wise changes of the cost: if $c$ and $c'$
-are two cost vectors such that $c'=(c_i', c_{-i})$ with $c_i' \leq c_i$, then
-we want $\tilde{L}(c')\geq \tilde{L}(c)$. Furthermore, we seek an approximation
-that can be computed in polynomial time.
+\EDP{} is NP-hard, but designing a mechanism for this problem will involve
+being able to find an approximation $\tilde{L}^*(c)$ of $OPT$ with the
+following three properties: first, it must be non-decreasing along
+coordinate-axis, second it must have a constant approximation ratio to $OPT$
+and finally, it must be computable in polynomial time.
 
 This approximation will be obtained by introducing a concave optimization
 problem with a constant approximation ratio to \EDP{}
@@ -15,125 +14,58 @@ object of (Section~\ref{sec:monotonicity}).
 
 \subsection{A concave relaxation of \EDP}\label{sec:concave}
 
-Let us introduce a new function $L$:
-\begin{equation}\label{eq:our-relaxation}
-\forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq
-\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right),
-\end{equation}
-
-This function is a relaxation of the value function $V$ defined in
-\eqref{modified} in the following sense: $L(\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
-a relaxation. We define:
-\begin{equation}\tag{$P_c$}\label{eq:primal}
-    L^*_c \defeq \max_{\lambda\in[0, 1]^{n}}
-    \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
-    \leq B\right\}
-\end{equation}
-
-\begin{proposition}\label{prop:relaxation}
-     $   L^*(c) \leq 2 OPT
-        + 2\max_{i\in\mathcal{N}}V(i)$.
-\end{proposition}
+A classical way of relaxing combinatorial optimization problems is 
+\emph{relaxing by expectation}, using the so-called \emph{multi-linear}
+extension of the objective function $V$.
 
-The proof of this proposition follows the \emph{pipage rounding} framework of
-\citeN{pipage}.
-
-This framework uses the \emph{multi-linear} extension $F$ of the submodular
-function $V$. Let $P_\mathcal{N}^\lambda(S)$ be the probability of choosing the
+Let $P_\mathcal{N}^\lambda(S)$ be the probability of choosing the
 set $S$ if we select each element $i$ in $\mathcal{N}$ independently with
 probability $\lambda_i$:
 \begin{displaymath}
     P_\mathcal{N}^\lambda(S) \defeq \prod_{i\in S} \lambda_i
     \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i).
 \end{displaymath}
-Then, the \emph{multi-linear} extension $F$ is defined by:
-\begin{displaymath}
+Then, the \emph{multi-linear} extension $F$ of $V$ is defined as the
+expectation of $V$ under the probability distribution $P_\mathcal{N}^\lambda$:
+\begin{equation}\label{eq:multi-linear}
     F(\lambda) 
     \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big]
     = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)
-\end{displaymath}
+\end{equation}
 
-For \EDP{}  the multi-linear extension can be written:
-\begin{equation}\label{eq:multi-linear-logdet}
-    F(\lambda) = \mathbb{E}_{S\sim
-    P_\mathcal{N}^\lambda}\bigg[\log\det \big(I_d + \sum_{i\in S} x_i\T{x_i}\big) \Big].
+This function is an extension of $V$ in the following sense: $F(\id_S) = V(S)$ for all
+$S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$.
+
+\citeN{pipage} have shown how to use this extension to obtain approximation
+guarantees for an interesting class of optimization problems through the
+\emph{pipage rounding} framework, which has been successfully applied
+in \citeN{chen, singer-influence}. 
+
+However, for the specific function $V$ defined in \eqref{modified}, the
+multi-linear extension cannot be computed (and \emph{a fortiori} maximized) in
+polynomial time. Hence, we introduce a new function $L$:
+\begin{equation}\label{eq:our-relaxation}
+\forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq
+\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right),
 \end{equation}
 Note that the relaxation $L$ that we introduced in \eqref{eq:our-relaxation},
-follows naturally from the \emph{multi-linear} relaxation by swapping the
-expectation and the $\log\det$ in \eqref{eq:multi-linear-logdet}:
+follows naturally from the \emph{multi-linear} extension by swapping the
+expectation and $V$ in \eqref{eq:multi-linear}:
 \begin{displaymath}
     L(\lambda) = \log\det\left(\mathbb{E}_{S\sim
     P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right).
 \end{displaymath}
 
-The proof proceeds as follows:
-\begin{itemize}
-\item First, we prove that $F$ admits the following rounding 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}. This is stated and proven in
-Lemma~\ref{lemma:rounding} and allows us to bound $F$ in terms of $OPT$.
-\item Next, we prove the central result of bounding $L$  appropriately in terms
-of the multi-linear relaxation $F$ (Lemma \ref{lemma:relaxation-ratio}).
-\item Finally, we conclude the proof of Proposition~\ref{prop:relaxation} by
-combining Lemma~\ref{lemma:rounding} and Lemma~\ref{lemma:relaxation-ratio}.
-\end{itemize}
-
-\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')$.
+The optimization program \eqref{eq:non-strategic} extends naturally to such
+a relaxation. We define:
+\begin{equation}\tag{$P_c$}\label{eq:primal}
+    L^*_c \defeq \max_{\lambda\in[0, 1]^{n}}
+    \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
+    \leq B\right\}
+\end{equation}
 
-    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}
+The key property of the relaxation $L$, which is our main technical result, is
+that it has constant approximation ratios to the multi-linear extension $F$.
 
 \begin{lemma}\label{lemma:relaxation-ratio}
  %   The following inequality holds:
@@ -306,11 +238,77 @@ Having bound the ratio between the partial derivatives, we now bound the ratio $
     function $V$. Hence, the ratio is equal to 1 on the vertices.
 \end{proof}
 
-To conclude 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
+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}
+
+Using Lemma~\ref{lemma:rounding}, we can relate the multi-linear extension to
+$OPT$, and Lemma~\ref{lemma:relaxation-ratio} relates our relaxation $L$ to the
+multi-linear extension. Putting these together gives us the following result:
+
+\begin{proposition}\label{prop:relaxation}
+$L^*_c \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$.
+\end{proposition}
+
+\begin{proof}
+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}
@@ -329,43 +327,81 @@ that
     \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 lemma. \hspace*{\stretch{1}}\qed
+    Together, \eqref{eq:e1} and \eqref{eq:e2} imply the lemma.
+\end{proof}
 
-\subsection{A monotonous Newton's estimator}\label{sec:monotonicity}
+\subsection{A monotonous estimator}\label{sec:monotonicity}
 
-\textbf{TODO} Explain that we only get approximate monotonicity, but even
-that is not immediate since the variation induced by a change of cost on
-coordinate $i$ depends on the allocation at this coordinate which can be
-arbitrarily small.
+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:
 
-For the ease of presentation, we normalize the costs by dividing them by the
-budget $B$ so that the budget constraint in \eqref{eq:primal} now reads
-$\T{c}\lambda\leq 1$.
+\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}
 
-\begin{proposition}\label{prop:monotonicity}
-    Let $\delta\in(0,1]$. For any $\varepsilon\in(0,1]$, there exists
-    an algorithm which computes an approximate solution $\tilde{L}^*_c$ to
-    \eqref{eq:primal} such that:
-    \begin{enumerate}
-        \item $|\tilde{L}^*_c - L^*_c| \leq \varepsilon$
-        \item for all $c' = (c_i', c_{-i})$ with $c_i'\leq c_i-\delta$, $\tilde{L}^*_c \leq \tilde{L}^*_{c'}$
-        \item the routine's running time is $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
-    \end{enumerate}
-\end{proposition}
+Note however that even though $L^*_c$ is non-decreasing along coordinate axis
+(if one of the cost decreases, then the feasible set of \eqref{eq:primal}
+increases), this will not necessarily be the case for an $\varepsilon$-accurate
+approximation of $L^*_c$ and Lemma~\ref{lemma:barrier} in itself is not
+sufficient to provide an approximation satisfying the
+properties requested at the beginning of Section~\ref{sec:approximation}.
 
-We consider a perturbation of \eqref{eq:primal} by introducing:
+The estimator we will construct in this section will have a slightly weaker
+form of coordinate-wise monotonicity: \emph{$\delta$-monotonicity}.
+
+\begin{definition}
+Let $f$ be a function from $\reals^n$ to $\reals$, we say that $f$ is
+\emph{$\delta$-increasing} iff:
+\begin{displaymath}
+    \forall x\in\reals^n,\;
+    \forall \mu\geq\delta,\;
+    \forall i\in\{1,\ldots,n\},\;
+    f(x+\mu e_i)\geq f(x)
+\end{displaymath}
+where $e_i$ is the $i$-th basis vector of $\reals^n$. We define
+\emph{$\delta$-decreasing} functions similarly.
+\end{definition}
+
+For the ease of presentation, we normalize the costs by dividing them by the
+budget $B$ so that the budget constraint in \eqref{eq:primal} now reads
+$\T{c}\lambda\leq 1$.  We consider a perturbation of \eqref{eq:primal} by
+introducing:
 \begin{equation}\tag{$P_{c, \alpha}$}\label{eq:perturbed-primal}
     L^*_c(\alpha) \defeq \max_{\lambda\in[\alpha, 1]^{n}}
     \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
-    \leq B\right\}
+    \leq 1\right\}
 \end{equation}
 Note that we have $L^*_c = L^*_c(0)$.  We will also assume that
 $\alpha<\frac{1}{n}$ so that \eqref{eq:perturbed-primal} has at least one
 feasible point: $(\frac{1}{n},\ldots,\frac{1}{n})$.
 
-Having introduced this perturbed problem, we show that its optimal value 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
+The $\delta$-decreasing approximation of $L^*_c$ is obtained by computing an
+approximate solution of \eqref{eq:perturbed-primal}.
+
+\begin{algorithm}[h]
+    \caption{}\label{alg:monotone}
+    \begin{algorithmic}[1]
+        \State $\alpha \gets \varepsilon(\delta+n^2)^{-1} $ 
+
+        \State Compute a $\frac{1}{2^{n+1}}\alpha\delta b$-accurate approximation of
+        $L^*_c(\alpha)$ using the barrier method
+    \end{algorithmic}
+\end{algorithm}
+
+\begin{proposition}\label{prop:monotonicity}
+    For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$,
+    Algorithm~\ref{alg:monotone} computes a $\delta$-decreasing,
+    $\varepsilon$-accurate approximation of $L^*_c$. The running time of the
+    algorithm is $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
+\end{proposition}
+
+
+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}.
 
@@ -560,20 +596,18 @@ In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2$.
 
 \subsubsection*{End of the proof of Proposition~\ref{prop:monotonicity}}
 
-Let $\varepsilon$ in $(0, 1]$. The routine works as follows: set $\alpha\defeq
-\varepsilon(\delta + n^2)^{-1}$ and return an approximation $\tilde{L}^*_c$ of
-$L^*_c(\alpha)$ with an accuracy $\frac{1}{2^{n+1}}\alpha\delta b$ computed by
-a standard convex optimization algorithm. Note that this choice of $\alpha$
-implies $\alpha<\frac{1}{n}$ as required.
-
+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 let $c' = (c_i', c_{-i})$ with $c_i'\leq c_i-\delta$, then:
+\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}}
@@ -587,14 +621,9 @@ the inner inequality follows from Lemma~\ref{lemma:monotonicity}.
     A\defeq\frac{\varepsilon\delta b}{2^{n+1}(\delta + n^2)}
 \end{displaymath}
 
-The function $L$ 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
-finding the maximum of $L$ to any precision $A$ can be done in
-$O(\log\log A^{-1})$ iterations. Note that:
+Note that:
 \begin{displaymath}
     \log\log A^{-1} = O\bigg(\log\log\frac{1}{\varepsilon\delta b} + \log n\bigg)
 \end{displaymath}
-Furthermore, each iteration of Newton's method can be done in time $O\big(poly(n,
-d)\big)$.\qed
+Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed
 \end{enumerate}