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?