diff options
Diffstat (limited to 'proof.tex')
| -rw-r--r-- | proof.tex | 6 |
1 files changed, 3 insertions, 3 deletions
@@ -335,7 +335,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$: \begin{algorithmic}[1] \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$ \State $x^* \gets \argmax_{x\in[0,1]^n} \{L_{\mathcal{N}\setminus\{i^*\}}(x) - \,|\, c(x)\leq\frac{B}{2}\}$ + \,|\, c(x)\leq B\}$ \Statex \If{$L(x^*) < CV(i^*)$} \State \textbf{return} $\{i^*\}$ @@ -344,7 +344,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$: \State $S \gets \emptyset$ \While{$c_i\leq \frac{B}{2}\frac{V(S\cup\{i\})-V(S)}{V(S\cup\{i\})}$} \State $S \gets S\cup\{i\}$ - \State $i \gets \argmax_{j\in\{1,\ldots,n\}\setminus S} + \State $i \gets \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\})-V(S)}{c_j}$ \EndWhile \State \textbf{return} $S$ @@ -382,7 +382,7 @@ The mechanism is budget feasible. Hence: \begin{displaymath} - V(i^*) \geq \frac{C}{C+1} OPT(V,\mathcal{N}, B) + V(i^*) \geq \frac{1}{C+1} OPT(V,\mathcal{N}, B) \end{displaymath} If the condition of the algorithm does not hold: |