Integrality gap and approximation ratio When we consider an approximation algorithm for a minimization problem, the integrality gap of an IP formulation for this problem gives a lower bound of an approximation ratio for certain class of algorithms (such as rounding or primal-dual algorithm).  In fact, there are many problems whose best approximation ratio matches the integrality gap.

Some algorithm may have a better approximation ratio than the integrality gap for some problem, but I don't know if such an example exists or not.  If the answer is yes, could you give some examples?

I know that some problems admit multiple mathematical formulations.  In such cases, consider the mathematical formulation with the smallest integrality gap, as long as it can be solved in polynomial time (perhaps some formulations may use separation oracles).

This question is related to [the question: The importance of Integrality Gap].
There are various examples in which a semidefinite programming relaxation allows an approximation that is superior to known integrality gaps for linear programming relaxations.

For example, the standard linear programming relaxation of max cut has an integrality gap of 1/2, and this is true even for much more sophisticated linear programming relaxations (c.f. de la Vega-Kenyon and Schoenebeck-Trevisan-Tulsiani), but the Goemans-Williamson SDP algorithm has approximation .878...

The Leighton-Rao linear programming relaxation of sparsest cut has an integrality gap $\Omega(\log n)$, but the Arora-Rao-Vazirani SDP algorithm has approximation $O(\sqrt{\log n})$.

Perhaps less well known, Karloff and Zwick shows that using SDP one can approximate Max 3SAT, in the version in which clauses can have 1, 2 or 3 literals, within 7/8, while Goemans and Williamson had studied a linear programming relaxation that they used to prove a 3/4 approximation (Yannakakis had given 3/4 approximation earlier by other methods), and the Goemans-Williamson LP relaxation of Max 3SAT is easily seen to have integrality gap 3/4.