How to define an approximation algorithm when it fails?
The usual way out in such circumstances is bicriteria approximation algorithms. Suppose that given a set of possible solutions $S$, a constraint function $f$, and an objective function $g$, your goal is to find a solution $x \in S$ such that $f(x) \leq 1$ minimizing $g(x)$. A bicriteria approximation algorithm will find a solution $x \in S$ such that $f(x) \leq \alpha$ and $g(x) \leq \beta \mathrm{OPT}$, where OPT is the optimal solution to the original problem.

The quality of bicriteria approximation algorithms is thus measured by two parameters. The parameter $\beta$ corresponds to the approximation ratio, and $\alpha$ controls by how much the solution violates the constraints.