One usually thinks about approximating solutions (with guarantees) to NP-hard problems. Is there any research going on in approximating problems already known to be in P? This might be a good idea for several reasons. Off the top of my head, an approximation algorithm may run with a much lower complexity (or even a much smaller constant), might use less space or might be much better parallelizable.

Also, schemes that provide time/accuracy tradeoffs (FPTAS's and PTAS's) might be very attractive for problems in P with lower bounds that are unacceptable on large inputs.

Two questions: is there anything that I'm missing that makes this obviously a bad idea? Is there research going on in developing a theory of these algorithms? If not, at least, is anyone familiar with individual examples of such algorithms?

One usually thinks about approximating solutions (with guarantees) to NP-hard problems. Is there any research going on in approximating problems already known to be in P? This might be a good idea for several reasons. Off the top of my head, an approximation algorithm may run with a much lower complexity (or even a much smaller constant), might use less space or might be much better parallelizable.

Also, schemes that provide time/accuracy tradeoffs (FPTAS's and PTAS's) might be very attractive for problems in P with lower bounds that are unacceptable on large inputs.

Three questions: is there anything that I'm missing that makes this obviously a bad idea? Is there research going on in developing a theory of these algorithms? If not, at least, is anyone familiar with individual examples of such algorithms?