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.
Space-approximation Trade-off
ds.algorithms;graph theory;approximation algorithms;space complexity