A friend of mine who has done some work in approximation algorithm asked me the following question:
Can you find a (graph theory) problem with a faster approximation (deterministic) algorithm?
For example, is there a linear-time constant-factor approximation algorithm for minimum spanning tree? Or is there is asymptotically faster algorithm for maximum flow?
Added later. Let me clarify a little bit. Approximation algorithm often refers to NP-hard problem. However, the definition still makes sense for any optimization problems, including those in P.