From b3c19ae2cbbdeec29f1c383b319119b0672e14f8 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 5 Nov 2012 17:53:19 +0100
Subject: Spell check in main.tex

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

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index b1f6519..eb1b477 100644
--- a/main.tex
+++ b/main.tex
@@ -87,7 +87,7 @@ problems, Chen et al.~\cite{chen} %for \textsc{Knapsack} and Singer
 propose comparing
 $V(i^*)$ to %$OPT(R_{\mathcal{N}\setminus\{i\}}, B)$, where $R$ denotes 
 the optimal value of a \emph{fractional relaxation} of the function $V$ over the set
-$\mathcal{N}$. A fuction $R:[0, 1]^{n}\to\reals_+$ defined on the hypercube  $[0, 1]^{n}$ is a fractional relaxation of $V$
+$\mathcal{N}$. A function $R:[0, 1]^{n}\to\reals_+$ defined on the hypercube  $[0, 1]^{n}$ is a fractional relaxation of $V$
 over the set $\mathcal{N}$ if %(a) $R$ is a function defined on the hypercube $[0, 1]^{n}$ and (b) 
   $R(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where
 $\id_S$ denotes the indicator vector of $S$. The optimization program
@@ -184,7 +184,7 @@ characterization from Singer \cite{singer-mechanisms} gives a formula to
 
 We can now state our main result:
 \begin{theorem}\label{thm:main}
-    The allocation described in Algorithm~\ref{mechanism}, along with threshold payments, is truthful, individiually rational 
+    The allocation described in Algorithm~\ref{mechanism}, along with threshold payments, is truthful, individually rational 
     and budget feasible. Furthermore, for any $\varepsilon>0$, the mechanism
     has  complexity $O\left(\text{poly}(n, d,
     \log\log \varepsilon^{-1})\right)$ and returns a set $S^*$ such that:
@@ -199,7 +199,7 @@ We can now state our main result:
 Note that this implies we construct a poly-time mechanism with accuracy arbitrarily close to 19.68, by taking $\varepsilon = \ldots$\stratis{fix me}.
 In addition, we prove the following lower bound.
 \begin{theorem}\label{thm:lowerbound}
-There is no $2$-approximate, truthful, budget feasible, individionally rational mechanism for EDP. 
+There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. 
 \end{theorem}
 %\stratis{move the proof as appropriate}
 \begin{proof}
-- 
cgit v1.2.3-70-g09d2

