alpha,beta

2 files changed, 4 insertions, 4 deletions

diff --git a/appendix.tex b/appendix.tex
index 904bd45..5cb60f8 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -510,10 +510,10 @@ an \emph{almost-dominant} \cite{schummer2004almost} strategy. Formally, let $c_{
     B.\label{budget}$
 
 
-   \item \emph{Approximation Ratio.} The value of the allocated set  should not
+   \item \emph{$(\alpha,\beta)$-approximation.} The value of the allocated set  should not
     be too far from the optimum value of the full information case, as given by  \eqref{eq:non-strategic}. 
-Formally, there must exist some $\alpha\geq 1$
-    such that $OPT \leq \alpha V(S(p))$, where     $OPT = \max_{S\subseteq\mathcal{N}} \left\{V(S) \;\mid \;
+Formally, there must exist some $\alpha\geq 1$ and $\beta>0$
+    such that $OPT \leq \alpha V(S(p))+\beta$, where     $OPT = \max_{S\subseteq\mathcal{N}} \left\{V(S) \;\mid \;
     \sum_{i\in S}c_i\leq B\right\}$.
 
  %   The approximation ratio captures the \emph{price of truthfulness}, \emph{i.e.},  the relative value loss incurred by adding the truthfulness constraint. % to the value function maximization.
diff --git a/main.tex b/main.tex
index 099d1d4..7fca12a 100644
--- a/main.tex
+++ b/main.tex
@@ -70,7 +70,7 @@ Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the a
     For any $\delta\in(0,1]$, and any $\epsilon\in (0,1]$,  there exists a $\delta$-truthful, individually rational
     and budget feasible mechanim for \EDP{} that runs in time
     $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$
-    and returns
+    and allocates
     a set $S^*$ such that
 %    \begin{align*}
        $ OPT