approximation algorithm with polynomial complexity

Question

It might be a silly question, I do take a carefully read about approximation algorithm through coursenotes, but when I saw the words "approximation algorithm with polynomial complexity", I can't understand what it means, I searched a lot and here is my assumption.

First, for some NPc or NP hard problem, we can try to solve them approximately, because there is no optimization algorithm right now. So compared with some opotimal solution theoretically, some optimazation problem can use approximation algorithm to get an approximation solution, such like vertex covering problem.

Then it is the term polynomial complexity, an algorithm is polynomial if for some k>0, its running time on inputs of size n is O(n^k).

So is "approximation algorithm with polynomial complexity" means an approximation algorithm that whose complexity is in polynomial time? So is it means there are approximation algorithm that has other complexity such as exponential complexity.

By the way, through the approximation algorithm for vertex covering problem, I know what the algorithm is (briefly it is takes an arbitrary edge from subset E' of all possible set of edges, add two vertax at set S and remove all edge who has the same vertex with that arbitrary edge and continue until E' is empty). But how to observe it is polynomial complexity or what?

I really apprexiate if someone can solve my confusion.

Answer 1

As you say, we believe there is no polynomial-time algorithm for solving an NP-hard problem. So if we wanted to have a polynomial-time algorithm, it seems like we need to give up the hope of always finding an optimal solution. So you are right: typically, we strive to find approximation algorithms that run in time polynomial in the input size. But sure, there is nothing that prevents you from considering approximation algorithms that run in exponential-time (or for example in FPT-time for some parameter).

Sometimes these approximation algorithms are very simple to state. This is perhaps often the case for greedy algorithms, like the one you mention for vertex cover. To see that it runs in time polynomial in the size of the input graph, you need to perform a runtime analysis in the usual way.

Answer 2

An "approximation algorithm with polynomial complexity" means just that: an approximation algorithm which complexity is polynomial. As you mentioned, an algorithm has polynomial complexity if $\exists k \mid T(n) = O(n^k)$. To ensure that your algorithm has polynomial complexity, you need to go back to the $O$-notation definition and do a proper analysis.

The algorithm you mention happens to compute an appoximative solution for a problem: this is a characteristic. However, The fact that it has polynomial complexity is a property. While most used approximation algorithms have polynomial complexity or less, nothing ensures that this is the case for every approximation algorithm.