Given a planar graph decide whether this graph can be colored with 3 colors. This is an NP-complete problem. But it is well known that any planar graph can be colored with 4 colors. So if we define our function f as the identity function, we have that if the original instance is 3-colorable then the optimal measure is equal to 3. On the other hand if the original instance is not 3-colorable the optimal measure of this graph is equal to 4. Since 4 can be written 3(1+1/3), we have a gap equal to 1/3. This implies that this problem cannot be approximated within a performance ratio smaller then 4/3, unless NP=P.

---