# Approximation algorithms used in exact algorithms

Approximation algorithms might give output up to some constant factor. This is a bit less satisfying than exact algorithms.

However, constant factors are ignored in time complexity.

So I wonder if the following trick is possible or was used, to solve some problem $B \circ A$:

1. Use an approximation algorithm solving problem $A$ to get solution $S$ within constant factor;
2. Use an exact algorithm, solving problem $B$, whose runtime depends on weight of $S$ but works as long as $S$ is a correct solution.

This way the approximation is a "subprocedure" of an exact algorithm, and the constant factor lost in step 1 is swallowed in step 2.

-
Crossposted to cstheory – sdcvvc Dec 30 '11 at 7:39