1
$\begingroup$

Is it possible for an approximation algorithm (for minimization optimization problem) to obtain smaller approximation ratios for inputs of larger size? For example, is $1/n$- or $1/\log n$-APX reasonable? If it is, do you know any natural problems?

$\endgroup$

1 Answer 1

1
$\begingroup$

In most cases it is possible to artificially enlarge an instance. For example, if you want to solve MAX-CLIQUE, you can add an independent set. In these circumstances, the approximation ratio cannot improve as the size of the instance gets larger. However, it is possible that there are some natural problems in which the phenomenon you describe does occur.

$\endgroup$
2
  • $\begingroup$ Thanks. Are you aware of any such natural problems? $\endgroup$
    – hengxin
    May 23, 2017 at 1:54
  • $\begingroup$ Unfortunately not. $\endgroup$ May 23, 2017 at 5:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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