diff options
| -rw-r--r-- | main.tex | 86 |
1 files changed, 36 insertions, 50 deletions
@@ -46,7 +46,7 @@ maximum value: \end{displaymath} then the following inequality holds: \begin{displaymath} - OPT(V,\mathcal{N},B) \leq \frac{5e}{e-1}\max\big\{ V(S_G), V(i^*)\big\} +OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big) \end{displaymath} \end{lemma} @@ -72,7 +72,7 @@ Here, we will use the following relaxation of the value function \eqref{vs}. Let us define the function $L_\mathcal{N}$: \begin{displaymath} \forall\lambda\in[0,1]^{|\mathcal{N}|}\,\quad L_{\mathcal{N}}(\lambda) \defeq - \log\det\left(I_d + \mu\sum_{i\in\mathcal{N}} \lambda_i x_i \T{x_i}\right) + \log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i \T{x_i}\right) \end{displaymath} Our mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. @@ -114,20 +114,12 @@ We can now state the main result of this section: \begin{theorem}\label{thm:main} The mechanism described in Algorithm~\ref{mechanism} is truthful, individually rational and budget feasible. Furthermore, choosing: - \begin{multline*} - C = C^* = \frac{5e-1 + C_\mu(2e+1)}{2C_\mu(e-1)}\\ - + \frac{\sqrt{C_\mu^2(1+2e)^2 - + 2C_\mu(14e^2+5e+1) + (1-5e)^2}}{2C_\mu(e-1)} - \end{multline*} + \begin{displaymath} + C = C^* = \frac{12e-1 + \sqrt{160e^2-48e + 9}}{2(e-1)} + \end{displaymath} we get an approximation ratio of: - \begin{multline*} - 1 + C^* = \frac{5e-1 + C_\mu(4e-1)}{2C_\mu(e-1)}\\ - + \frac{\sqrt{C_\mu^2(1+2e)^2 - + 2C_\mu(14e^2+5e+1) + (1-5e)^2}}{2C_\mu(e-1)} - \end{multline*} - where: \begin{displaymath} - C_\mu = \frac{\log(1+\mu)}{2\mu} + 1 + C^* = \frac{14e-3 + \sqrt{160e^2-48e + 9}}{2(e-1)}\simeq 18.68 \end{displaymath} \end{theorem} @@ -221,8 +213,8 @@ Hence, the total payment is bounded by: \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{e}{e-1}\left( 3 + \frac{12e}{C\cdot - C_\mu(e-1) -5e +1}\right)\right) + 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: @@ -232,7 +224,6 @@ Hence, the total payment is bounded by: \end{displaymath} \end{lemma} - \begin{proof} If the condition on line 3 of the algorithm holds, then: @@ -254,22 +245,22 @@ Hence, the total payment is bounded by: 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\cdot C_\mu} - \big(2 OPT(V,\mathcal{N}, B) + V(i^*)\big)\\ - & \leq \frac{1}{C\cdot C_\mu}\left(\frac{2e}{e-1}\big(3 V(S_G) + 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{6e}{C\cdot C_\mu(e-1)- 5e + 1} V(S_G) + 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{e}{e-1}\left( 3 + \frac{12e}{C\cdot - C_\mu(e-1) -5e +1}\right) V(S_G) + 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} @@ -280,7 +271,7 @@ The optimal value for $C$ is: This equation has two solutions. Only one of those is such that: \begin{displaymath} - C\cdot C_\mu(e-1) -5e +1 \geq 0 + 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. @@ -336,7 +327,7 @@ probabilities $P_\mathcal{N}$: & = \log\det \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[A(S)\big]\\ & = \log\det\left(\sum_{S\subseteq N} P_\mathcal{N}^\lambda(S)A(S)\right)\\ - & = \log\det\left(I_d + \mu\sum_{i\in\mathcal{N}} + & = \log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_ix_i\T{x_i}\right)\\ & \defeq \log\det \tilde{A}(\lambda) \end{align*} @@ -365,7 +356,7 @@ We will also use the \emph{multi-linear extension}: \end{proof} It has been observed already (see for example \cite{dughmi}) that the -multilinear extension presents the cross-convexity property: it is convex along +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 @@ -432,7 +423,7 @@ the points remain feasible during the trade. The following inequality holds: \begin{displaymath} \forall\lambda\in[0,1]^{|\mathcal{N}|},\; - \frac{\log\big(1+\mu\big)}{2\mu} + \frac{1}{2} \,L_\mathcal{N}(\lambda)\leq F_\mathcal{N}(\lambda)\leq L_{\mathcal{N}}(\lambda) \end{displaymath} @@ -440,12 +431,8 @@ the points remain feasible during the trade. \begin{proof} - We will prove that: - \begin{displaymath} - \frac{\log\big(1+\mu\big)}{2\mu} - \end{displaymath} - is a lower bound of the ratio $\partial_i F_\mathcal{N}(\lambda)/\partial_i - L_\mathcal{N}(\lambda)$. + 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)$. This will be enough to conclude, by observing that: \begin{displaymath} @@ -455,7 +442,7 @@ the points remain feasible during the trade. {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L_\mathcal{N}(0)} \end{displaymath} and that an interior critical point of the ratio - $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$ is defined by: + $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 @@ -502,14 +489,14 @@ the points remain feasible during the trade. \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 + \mu \T{x_i}A(S)^{-1}x_i\Big) + \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) - = \mu \T{x_i}\tilde{A}(\lambda)^{-1}x_i + = \T{x_i}\tilde{A}(\lambda)^{-1}x_i \end{displaymath} Using the following inequalities: @@ -526,36 +513,35 @@ the points remain feasible during the trade. \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 + \mu \T{x_i}A(S)^{-1}x_i\Big)\\ + \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 + \mu \T{x_i}A(S)^{-1}x_i\Big)\\ + \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 + \mu \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\ + \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 + \mu \T{x_i}A(S)^{-1}x_i\Big)\\ + \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} - \mu \T{x_i}A(S)^{-1}x_i \leq \mu + \T{x_i}A(S)^{-1}x_i \leq 1 \end{displaymath} Moreover: \begin{displaymath} - \forall x\leq\mu,\; \log(1+x)\geq - \frac{\log\big(1+\mu\big)}{\mu} x + \forall x\leq 1,\; \log(1+x)\geq x \end{displaymath} Hence: \begin{displaymath} \partial_i F_\mathcal{N}(\lambda) \geq - \frac{\log\big(1+\mu\big)}{2\mu} + \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} @@ -563,18 +549,18 @@ the points remain feasible during the trade. positive definite matrices: \begin{align*} \partial_i F_\mathcal{N}(\lambda) &\geq - \frac{\log\big(1+\mu\big)}{2\mu} + \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{\log\big(1+\mu\big)}{2\mu} - \partial_i L_\mathcal{N}(\lambda) + & \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 \frac{1}{C_\mu}\big(2 OPT(V,\mathcal{N},B) - + \max_{i\in\mathcal{N}}V(i)\big) + OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B) + + 2\max_{i\in\mathcal{N}}V(i) \end{displaymath} \end{lemma} @@ -584,7 +570,7 @@ the points remain feasible during the trade. 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 \frac{1}{C_\mu} + L_\mathcal{N}(\lambda^*) \leq 2 F_\mathcal{N}(\bar{\lambda}) \end{equation} |