I have an NP-hard problem P where we are trying to minimize some objective function subject to some constraints. Problem P is very hard in the sense that even finding a feasible solution is NP-hard! (i.e., finding a solution that satisfies the constraints is NP-hard).
Let OPT denotes the optimal algorithm for P. That is, OPT will return, given an instance of P, the best possible solution, or will report none exist. Now, suppose I designed an approximation algorithm, denoted ALG, that solves P (of course not to optimality).
Given an instance I1 of P, ALG may fail to find a feasible solution when actually one exists and of course OPT finds it. So, if I would like to measure the performance of ALG in terms of its approximation ratio, how would I do that? Should I ignore the instance I1? As far as I know, an approximation algorithm, by definition, must return, for any instance of the problem, a solution that has a bounded value compared to the optimal value. But in this case, given an instance of P, ALG may not be able to find any value and hence reports none.
For short, if an algorithm fails to find a solution to a problem, how do we measure its performance ratio? Is it even considered an approximation algorithm? Is there something related to this in the literature?