In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(2k-1)$-approximate distance between any pair of vertices in the graph.

At a fundamental level, this construction achieves a space-approximation trade-off --- one can reduce the space requirements at the cost of a lower "quality" of the solution.

What other graph problems exhibit such a trade-off between space and approximation?

I am interested in the case of both static and dynamic, weighted and unweighted, undirected and directed graphs.

Thanks.

• Trade-off usually means a lower bound: if you make one thing smaller, then the other needs to be larger. Do you want an upper bound result (as in your example), or a lower bound result? – Yoshio Okamoto Mar 4 '13 at 7:46
• @YoshioOkamoto - An upper bound can "achieve" a trade-off --- an upper bound may not mean that the trade-off is essential (which is a lower bound question), but it can achieve one. Is that right? Irrespective of that, I am interested in both lower bounds and upper bounds. – Rachit Mar 4 '13 at 9:07