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$:


*

*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.

Question was answered at cstheory.
