Suppose that there is a specific instance of a graph for which the approximation ratio of an algorithm polynomially increases with the number of nodes of the graph, say the approximation ratio is $n^2$. Further, suppose that the number of nodes of that bad instance can be easily increased. For example, assume that the approximation ratio $n^2$ is obtained when nodes are distributed over the circumference of a circle and the number of nodes can be arbitrary large.

Then, is it correct to say the approximation ratio is unbounded? When an approximation ratio can be called unbounded?

  • $\begingroup$ For first question: Yes, see definition of PTAS, FPTAS and EPTAS, they are all unbounded approximation ratio and its running time related to the size of input and approximation ratio. For second question: the approximation ratio are called unbounded when you are able to have an infinite approximation algorithm for the problem. i.e. if you want a better ratio of the approximation algorithm for the problem, the more time you give to wait for an answer. see this and read first few pages in the introduction (win.tue.nl/~gwoegi/papers/ptas.pdf). $\endgroup$ – YOUSEFY Apr 25 at 11:32
  • $\begingroup$ @YOUSEFY Thanks for the hit and the link. I have two questions. I am not into algorithms and the questions may seem naive. first: as I told, assume that for a specific structure of a graph, the approximation ratio is $n^2$. This $n^2$ is clearly a lower bound, because there might be other configurations with a worse ratio. Then the term lower-bounded by $n^2$ seems correct rather than unbounded. $\endgroup$ – Mahdi Apr 25 at 21:28
  • $\begingroup$ @YOUSEFY Second, there exists may algorithms with ratio that scales with $n$, say $O(log(n))$. When $n$ increase, $O(log(n))$ goes to infinity. Why aren't they called unbounded? I mean $O(log(n))$, or they can be called and I am not aware of? $\endgroup$ – Mahdi Apr 25 at 21:29
  • $\begingroup$ For first question, if you have an approximation ratio of O(n) or O(log n), then it doesn't mean that this is a lower bound approximation ratio!! it says just we have an upper bound for the problem (assume that maximization and minimization problems have approximation ratio greater than 1). For example, set cover problem has an approximation ratio of O(log n). Now, if you want to show a lower bound for approximation algorithm of a problem, then this is another task. There is a paper of 40 pages I think about proof of no better than O(log n) for set cover. The same happens for other problems. $\endgroup$ – YOUSEFY Apr 27 at 2:08
  • $\begingroup$ if a problem has or doesn't have a unbounded approximation ratio, then you need to give a reduction from one of APX-hard problems. The second question is not clear for me. $\endgroup$ – YOUSEFY Apr 27 at 2:26

Your Answer

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

Browse other questions tagged or ask your own question.