For example can an approximation algorithm call a subroutine which is solving a NP-Hard problem? (like say its trying to find the longest path in some graph as an intermediate step) Is that allowed?

  • 1
    $\begingroup$ What do you think? In general, any algorithm may use any other algorithm as subrouting, and even itself. $\endgroup$ – Raphael Oct 1 '14 at 20:08

Depends. Typically, with "approximation algorithms" people understand algorithms that run in polynomial time and return a possibly non-optimal solution (with a formal guarantee on the solution quality). In this definition, no, you can't spend exponential time solving an NP-hard problem.

On the other hand, nothing is forcing you to consider polynomial time algorithms that return non-optimal solutions. In fact, it is interesting to consider algorithms that take exponential time, and still return non-optimal solutions. See for instance [1, 2].

[1] Cygan, Marek, Lukasz Kowalik, Marcin Pilipczuk, and Mateusz Wykurz. "Exponential-time approximation of hard problems." arXiv preprint arXiv:0810.4934 (2008).

[2] Cygan, Marek, Łukasz Kowalik, and Mateusz Wykurz. "Exponential-time approximation of weighted set cover." Information Processing Letters 109, no. 16 (2009): 957-961.


It depends entirely on what complexity you want your algorithm to have. For example, if you're trying to approximate an EXP-hard problem then a polynomial algorithm that uses an NP oracle might be acceptable; if you're trying to approximate something that's only NP-hard, using an NP oracle more than once would be potentially more expensive than just solving the problem exactly.


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.