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?

  • $\begingroup$ Is it even considered an approximation algorithm? Probably not. $\endgroup$ – Karolis Juodelė Nov 27 '16 at 7:18

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.