From 9a767039fd69ef1c8e2d65a6adc36fd5ae269e51 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 23 Oct 2012 15:13:51 -0700
Subject: Fix some typos

---
 proof.tex | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

(limited to 'proof.tex')

diff --git a/proof.tex b/proof.tex
index d8cacbf..843b18b 100644
--- a/proof.tex
+++ b/proof.tex
@@ -335,7 +335,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \begin{algorithmic}[1]
     \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
     \State $x^* \gets \argmax_{x\in[0,1]^n} \{L_{\mathcal{N}\setminus\{i^*\}}(x)
-                                    \,|\, c(x)\leq\frac{B}{2}\}$
+                                    \,|\, c(x)\leq B\}$
         \Statex
         \If{$L(x^*) < CV(i^*)$}
             \State \textbf{return} $\{i^*\}$
@@ -344,7 +344,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
             \State $S \gets \emptyset$
             \While{$c_i\leq \frac{B}{2}\frac{V(S\cup\{i\})-V(S)}{V(S\cup\{i\})}$}
                 \State $S \gets S\cup\{i\}$
-                \State $i \gets \argmax_{j\in\{1,\ldots,n\}\setminus S}
+                \State $i \gets \argmax_{j\in\mathcal{N}\setminus S}
                 \frac{V(S\cup\{j\})-V(S)}{c_j}$
             \EndWhile
             \State \textbf{return} $S$
@@ -382,7 +382,7 @@ The mechanism is budget feasible.
 
     Hence:
     \begin{displaymath}
-        V(i^*) \geq \frac{C}{C+1} OPT(V,\mathcal{N}, B)
+        V(i^*) \geq \frac{1}{C+1} OPT(V,\mathcal{N}, B)
     \end{displaymath}
 
     If the condition of the algorithm does not hold:
-- 
cgit v1.2.3-70-g09d2

