14
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Yoshio Okamoto
    Mar 4, 2013 at 7:46
  • 1
    $\begingroup$ @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. $\endgroup$
    – Rachit
    Mar 4, 2013 at 9:07

1 Answer 1

Reset to default
-2
$\begingroup$

this research appears to be active in a more applied sense than the theoretical one you mention (ie oracles etc) with "data streaming" algorithms which attempt to work with very large data through "sliding windows", with many graph algorithms considered, but it is indeed relatively new/recent, fitting in with "big data" research directions.

We have devised several algorithms for fundamental graph problems in the W-Stream model, including connected components, minimum spanning tree, biconnected components and single-source shortest paths. To the best of our knowledge, our algorithms are the first to allow effective space/passes tradeoffs for such problems in a data streaming setting.

this ref includes other refs/surveys which might be helpful.

Despite the heavy restrictions imposed by the [classical streaming] model, major success has been achieved for several data sketching and statistics problems, for which a constant number of passes and polylogarithmic working memory have been proven enough to find approximate solutions (see [4, 16, 17] and the extensive bibliographies in [7, 29]).

also:

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.