1
$\begingroup$

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.

  • 0
    Crossposted to [cstheory](http://cstheory.stackexchange.com/questions/9537)2011-12-30

1 Answers 1

0

Question was answered at cstheory.