diff options
| author | Thibaut Horel <thibaut.horel@gmail.com> | 2013-04-16 15:43:50 +0200 |
|---|---|---|
| committer | Thibaut Horel <thibaut.horel@gmail.com> | 2013-04-16 15:43:50 +0200 |
| commit | 6cc7d966aca5cd760309881a90125a9058cc3e61 (patch) | |
| tree | 0a58fabadd10110e3655244085a820abcc2192e6 /main.tex | |
| parent | f408c518fb2f6d0ec15c50c9e9be800b4311eff8 (diff) | |
| download | recommendation-6cc7d966aca5cd760309881a90125a9058cc3e61.tar.gz | |
Fix some typos and inconsistent notations
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 6 |
1 files changed, 3 insertions, 3 deletions
@@ -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} |
