Greedy vs LP Approximation I wanted to know whether Greedy approximation algorithms can outperform LP relaxation and rounding based algorithms. Specifically, can it beat the integrality gap of a 'reasonable' LP relaxation, (e.g. the natural relaxation of the ILP by relaxing variables $x_i\in\{1,0\}$ to $x\geq 0$). 

For an example, if we consider the Setcover problem with universe set $U$ s.t. $|U|=n$ with max frequency of an element $f$, the greedy algorithm gives an $O(\mathrm{log}~n)$ approximation. Whereas LP relaxation can give an $f$ approximation with deterministic rounding. But we know that the integrality gap is $\Omega(\mathrm{log}~n)$ for the general LP formulation. Indeed through a randomized rounding technique we can achieve a $O(\mathrm{log}~n)$ approximation w.h.p. So the greedy is almost as good as the LP relaxation.

Does anyone know of an instance of NP Hard problem having approximations using greedy algorithm which is better than the integrality gap? Please point out the references if known. It will be great if the problem is well studied.
Well, there are cases where LP gives you no useful information. Consider a graph $G$ with $n$ vertices, and the problem of finding a maximum independent set in $G$. The LP gives you a solution of value at least $n/2$ (give every vertex a value of $1/2$). But the optimal independent set might be of size between $1$ and $n$.

On the other hand, the greedy algorithm does give useful results in some cases. For example, if the number of edges is $m \ll n^2$, then the greedy algorithm would give you an independent set of size $\Omega(n^2/m)$ (always pick the vertex that has the smallest numbeer of neighbors).