Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Crossposted to cstheory –  sdcvvc Dec 30 '11 at 7:39

1 Answer 1

up vote 0 down vote accepted

Question was answered at cstheory.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.