From f2b06157054bf990d2b429792adce3fc0a370fc9 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Wed, 31 Oct 2012 17:34:41 +0100
Subject: Adapt the proof in the case where \mu = 1

---
 main.tex | 86 +++++++++++++++++++++++++++-------------------------------------
 1 file changed, 36 insertions(+), 50 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index bd57295..324c2f8 100644
--- a/main.tex
+++ b/main.tex
@@ -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}
 
-- 
cgit v1.2.3-70-g09d2

