We often seek approximate solutions to simple problems like finding shortest path in a graph, finding number of unique elements in a set. The constraint here is that the input is large and we want to solve the problem approximately using a single pass over the data. There are several "streaming" algorithms designed to achieve approximate solutions in linear/near-linear time.
One problem I worked on, is approximating betweenness centrality. This can be solved in O(nm)$O(nm)$ time on graphs with n$n$ vertices and m$m$ edges. A linear time algorithm giving a constant factor approximation to betweenness centrality is of very practical importance.
