summaryrefslogtreecommitdiffstats
path: root/main.tex
diff options
context:
space:
mode:
authorThibaut Horel <thibaut.horel@gmail.com>2013-04-16 15:43:50 +0200
committerThibaut Horel <thibaut.horel@gmail.com>2013-04-16 15:43:50 +0200
commit6cc7d966aca5cd760309881a90125a9058cc3e61 (patch)
tree0a58fabadd10110e3655244085a820abcc2192e6 /main.tex
parentf408c518fb2f6d0ec15c50c9e9be800b4311eff8 (diff)
downloadrecommendation-6cc7d966aca5cd760309881a90125a9058cc3e61.tar.gz
Fix some typos and inconsistent notations
Diffstat (limited to 'main.tex')
-rw-r--r--main.tex6
1 files changed, 3 insertions, 3 deletions
diff --git a/main.tex b/main.tex
index e112470..d8635db 100644
--- a/main.tex
+++ b/main.tex
@@ -1,7 +1,7 @@
\label{sec:main}
In this section we present our mechanism for \SEDP. Prior approaches to budget
-feasible mechanisms for sudmodular maximization build upon the full information
+feasible mechanisms for submodular maximization build upon the full information
case, which we discuss first.
\subsection{Submodular Maximization in the Full Information Case}
@@ -67,7 +67,7 @@ $\mathcal{N}$ if $L(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S
denotes the indicator vector of $S$. The optimization program
\eqref{eq:non-strategic} extends naturally to such relaxations:
\begin{align}
- OPT' = \argmax_{\lambda\in[0, 1]^{n}}
+ OPT' \defeq \max_{\lambda\in[0, 1]^{n}}
\left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
\leq B\right\}\label{relax}
\end{align}
@@ -102,7 +102,7 @@ We show this by establishing that $L$ is within a constant factor from the so-ca
\begin{algorithmic}[1]
\State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$
\State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
- \State $OPT'_{-i^*} \gets \argmax_{\lambda\in[0,1]^{n}} \{L(\lambda)
+ \State $OPT'_{-i^*} \gets \max_{\lambda\in[0,1]^{n}} \{L(\lambda)
\mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$
\Statex
\If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c}