0
$\begingroup$

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 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?

$\endgroup$

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.