diff options
Diffstat (limited to 'approximation.tex')
| -rw-r--r-- | approximation.tex | 327 |
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} |