Question

Can approximation algo give answer less than optimal solution

Answer 1

Explanation:

The ratio bound of an approximation algorithm is never less than 1, since C/C* < 1 implies C*/C > 1. An optimal algorithm has ratio bound 1, and an approximation algorithm with a large ratio bound may return a solution that is very much worse than optimal.