Need a graph theory problem with nontrivial faster approximation algorithm 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.
 A: One example would be maximum matching. A matching $M$ is a set of pairwise nonadjacent edges. It can be solved in polynomial time, but no linear time algorithm is known. On the other hand, the greed algorithm, that adds edges one by one if no adjacent edge has been added before, is a 2-approximation and can be implemented in linear time.
A: There are approximation algorithms for the (metric) travelling salesman problem, that is, where the distances are symmetric and obey the triangle inequality.
For example, Christofides algorithm finds a path that is within a factor of 3/2 of the optimal solution length. Other special cases have even better approximations, such as the Euclidean TSP (where the vertices are points in $\mathbb{R}^d$) or the $(1, 2)$--TSP (where the edges all have length 1 or 2).
Although there is no constant factor approximation algorithm for TSP in general (without the metric assumption).
More generally this is known as the class of APX-hard or APX-complete problems. You can find more about this on the Complexity Zoo.
