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$:
- Use an approximation algorithm solving problem $A$ to get solution $S$ within constant factor;
- 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.