Proof of the approximation ratio

1 files changed, 50 insertions, 4 deletions

diff --git a/proof.tex b/proof.tex
index b38d7e6..d8cacbf 100644
--- a/proof.tex
+++ b/proof.tex
@@ -205,7 +205,8 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \begin{displaymath}
         \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}
         \sim_{\lambda\rightarrow 0}
-        \frac{\sum_{i\in S}\partial_i F_\mathcal{N}(0)}{\sum_{i\in S}\partial_i L_\mathcal{N}(0)}
+        \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F_\mathcal{N}(0)}
+        {\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:
@@ -324,8 +325,8 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
 
 \begin{lemma}
     \begin{displaymath}
-        OPT(L_\mathcal{N}, B) \leq \frac{1}{C}OPT(V,\mathcal{N},B)
-        + \max_{i\in\mathcal{N}}V(i)
+        OPT(L_\mathcal{N}, B) \leq \frac{1}{C_\kappa}\big(2 OPT(V,\mathcal{N},B)
+        + \max_{i\in\mathcal{N}}V(i)\big)
     \end{displaymath}
 \end{lemma}
 
@@ -362,10 +363,55 @@ The mechanism is budget feasible.
 \begin{lemma}
     Let us denote by $S_M$ the set returned by the mechanism. Then:
     \begin{displaymath}
-        V(S_M) \geq C\cdot OPT(V, \mathcal{N}, B)
+        V(S_M) \geq ?\cdot OPT(V, \mathcal{N}, B)
     \end{displaymath}
 \end{lemma}
 
+\begin{proof}
+
+    If the condition on line 3 of the algorithm holds, then:
+    \begin{displaymath}
+        V(i^*) \geq \frac{1}{C}L(x^*) \geq
+        \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B)
+    \end{displaymath}
+
+    But:
+    \begin{displaymath}
+        OPT(V,\mathcal{N},B) \leq OPT(V,\mathcal{N}\setminus\{i\}, B) + V(i^*)
+    \end{displaymath}
+
+    Hence:
+    \begin{displaymath}
+        V(i^*) \geq \frac{C}{C+1} OPT(V,\mathcal{N}, B)
+    \end{displaymath}
+
+    If the condition of the algorithm does not hold:
+    \begin{align*}
+        V(i^*) & \leq \frac{1}{C}L(x^*) \leq \frac{1}{C\cdot C_\kappa}
+        \big(2 OPT(V,\mathcal{N}, B) + V(i^*)\big)\\
+        & \leq \frac{1}{C\cdot C_\kappa}\left(\frac{2e}{e-1}\big(3 V(S_M)
+        + 2 V(i^*)\big)
+        + V(i^*)\right)
+    \end{align*}
+    
+    Thus:
+    \begin{align*}
+        V(i^*) \leq \frac{6e}{C\cdot C_\kappa(e-1)- 5e + 1} V(S_M)
+    \end{align*}
+
+    Finally, using again that:
+    \begin{displaymath}
+        OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big(3 V(S_M) + 2 V(i^*)\big)
+    \end{displaymath}
+    
+    We get:
+    \begin{displaymath}
+        OPT(V, \mathcal{N}, B) \leq \frac{e}{e-1}\left( 3 + \frac{12e}{C\cdot
+        C_\kappa(e-1) -5e  +1}\right) V(S_M)
+    \end{displaymath}
+
+\end{proof}
+
 \begin{theorem}
     The mechanism is individually rational, truthful and has an approximation
     ratio of