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
$\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$
  • $\begingroup$ Thanks. Are you aware of any such natural problems? $\endgroup$ – hengxin May 23 '17 at 1:54
  • $\begingroup$ Unfortunately not. $\endgroup$ – Yuval Filmus May 23 '17 at 5:01

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.