From 705f11ce5e6cf6dbd41e8a055743d711b8f8fbdb Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 5 Nov 2012 16:27:15 +0100
Subject: More fixes, reapply some lost changes overwritten by previous merge

---
 main.tex | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 482b1c9..b1f6519 100644
--- a/main.tex
+++ b/main.tex
@@ -19,8 +19,12 @@ included in $S$ is the one with the highest \emph{marginal-value-per-cost}:
 \end{align}
 This process terminates when no more items can be added to $S$ using \eqref{greedy} under budget $B$. This is the generalization of the \emph{value-per-cost} ratio used in the greedy approximation
 algorithm for \textsc{Knapsack}. However, in contrast to \textsc{Knapsack}, for general submodular
-functions, the marginal value  of an element in \eqref{greedy} depends on the set to which it the element is added.
-%
+functions, the marginal value  of an element in \eqref{greedy} depends on the set to which the element is added.
+Similarly, the value of an element depends on the set in which it is
+considered. However, in the following, the value of an element $i$ will refer to
+its value as a singleton set: $V(\{i\})$. If there is no ambiguity, we will write
+$V(i)$ instead of $V(\{i\})$.
+
 Unfortunately, even for the full information case, the greedy algorithm gives an
 unbounded approximation ratio. Let  $i^*
 = \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value.
@@ -28,7 +32,7 @@ unbounded approximation ratio. Let  $i^*
 %It has been noted by Khuller \emph{et al.}~\cite{khuller} that 
  For the maximum
 coverage problem, taking the maximum between the greedy solution and $V(i^*$)
-gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller} . In the general case, 
+gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller}. In the general case, 
 \junk{we have the
 following result from Singer \cite{singer-influence} which follows from
 Chen \emph{et al.}~\cite{chen}: \stratis{Is it Singer or Chen? Also, we need to introduce $V(i)$ somewhere...}
@@ -85,8 +89,8 @@ $V(i^*)$ to %$OPT(R_{\mathcal{N}\setminus\{i\}}, B)$, where $R$ denotes
 the optimal value of a \emph{fractional relaxation} of the function $V$ over the set
 $\mathcal{N}$. A fuction $R:[0, 1]^{n}\to\reals_+$ defined on the hypercube  $[0, 1]^{n}$ is a fractional relaxation of $V$
 over the set $\mathcal{N}$ if %(a) $R$ is a function defined on the hypercube $[0, 1]^{n}$ and (b) 
-  $R(\mathbf{1}_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where
-$\mathbf{1}_S$ denotes the indicator vector of $S$. The optimization program
+  $R(\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}}
-- 
cgit v1.2.3-70-g09d2

