I am trying to understand whether the Greedy algorithm guarantee for maximization of monotone submodular functions with a cardinality constraint is a lower bound on the performance. This is the context: Greedy algorithm algorithm starts with the empty set $A_0$ and then repeats the following step for $i=0,...,(k−1)$: $$A_{i+1} = A_{i} \cup \left\{ argmax_{v \in V \setminus A_i} f(A_i \cup \{v\}) \right\}$$ where $$\left\{ argmax_{v \in V \setminus A_i} f(A_i \cup \{v\}) \right\} = \left\{ argmax_{v \in V \setminus A_i} \Delta(v | A_i) \right\}$$
Let
- $A_i=(v_1,v_2,...,v_i)$ be the the chain formed by the greedy algorithm, as defined above.
- $A^*=(v^*_1,v^*_2,...,v_i)$ be the optimal solution, in an arbitrary order.
- $f$ be a monotone, submodular, non-negative function.
- $OPT = f(A^*)$ be the value of the optimal solution.
The Greedy algorithm proves that: $$f(A_k) \geq (1 - 1/e) OPT$$
We note that $1 - 1/e \approx 0.63$. This means: $$f(A_k) \geq 0.63 OPT$$
I do not understand how the value of the solution provided by the Greedy algorithm, $f(A_k)$, can be lower bounded by $0.63 OPT$. Shouldn't this be the other way around, because the Greedy algorithm cannot find an optimal solution in polynomial time? Does this mean the solution provided by the Greedy will always be greater than $0.63 OPT$ but less than $OPT$?
