From 6cc7d966aca5cd760309881a90125a9058cc3e61 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Tue, 16 Apr 2013 15:43:50 +0200 Subject: Fix some typos and inconsistent notations --- main.tex | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'main.tex') 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} -- cgit v1.2.3-70-g09d2