Open Problems:74 - Revision history

Krzysztof Onak: Updating header

2016-01-18T18:43:47Z

Updating header

Krzysztof Onak: Krzysztof Onak moved page Waiting:Robi to Open Problems:74 without leaving a redirect: Moving to main list of problems

2016-01-18T18:40:35Z

Krzysztof Onak moved page Waiting:Robi to Open Problems:74 without leaving a redirect: Moving to main list of problems

Ccanonne at 16:33, 16 January 2016

2016-01-16T16:33:02Z

Ccanonne at 16:32, 16 January 2016

2016-01-16T16:32:29Z

74.108.164.245 at 14:11, 15 January 2016

2016-01-15T14:11:26Z

74.108.164.245 at 14:10, 15 January 2016

2016-01-15T14:10:11Z

Krzysztof Onak: Small edits

2016-01-12T22:01:55Z

Small edits

Ccanonne at 18:09, 12 January 2016

2016-01-12T18:09:52Z

Gautam Kamath at 05:04, 12 January 2016

2016-01-12T05:04:02Z

Gautam Kamath at 05:03, 12 January 2016

2016-01-12T05:03:31Z

@@ Line 1: / Line 1: @@
 {{Header
 |source=baltimore16
 |who=Robert Krauthgamer

@@ Line 17: / Line 17: @@
 * A randomized data structure for $(1+\varepsilon)$-approximating any cut value (or Rayleigh quotient) in $G$, which is more space-efficient than the known graphical representation, can be found in {{cite|AndoniCKQWZ-16}}.
-* For a given graph $G$ with $k$ terminals, the exact values of all the minimum cuts between subsets of terminals can be stored simply as a list of $2^k$ numbers. The best graphical representation known is of size roughly $2^{2^k}$ {{cite|HagerupKNR-98,KhanR-14}}.
+* For a given graph $G$ with $k$ terminals, the exact values of all the minimum cuts between subsets of terminals can be stored simply as a list of $2^k$ numbers. The best graphical representation known is of size roughly $2^{2^k}$ {{cite|HagerupKNR-98|KhanR-14}}.
 * A deterministic data structure for $(1+\varepsilon)$-approximating any multicommodity flow on a set of $k$ given terminals in $G$. There is no known graphical representation for this, whose size depends on $k$ and $\varepsilon$, but not on $G$ {{cite|AndoniGK-14}}.

← Older revision		Revision as of 16:32, 16 January 2016
Line 12:		Line 12:
	Thus for this problem, a very space-efficient data structure (perhaps even the best one) is itself a graph $G'$, and it encodes the desired values in a natural manner, just compute the same function (min $st$-cut) on $G'$.		Thus for this problem, a very space-efficient data structure (perhaps even the best one) is itself a graph $G'$, and it encodes the desired values in a natural manner, just compute the same function (min $st$-cut) on $G'$.
	But is this the case for all such functions on graphs, or is there a (natural) case where a potentially complicated data structure outperforms a graphical encoding? The question applies both to exact and approximate computations of the function.		But is this the case for all such functions on graphs, or is there a (natural) case where a potentially complicated data structure outperforms a graphical encoding? The question applies both to exact and approximate computations of the function.
		+
		+	'''Some relevant examples:'''
		+
		+	* A randomized data structure for $(1+\varepsilon)$-approximating any cut value (or Rayleigh quotient) in $G$, which is more space-efficient than the known graphical representation, can be found in {{cite\|AndoniCKQWZ-16}}.
		+
		+	* For a given graph $G$ with $k$ terminals, the exact values of all the minimum cuts between subsets of terminals can be stored simply as a list of $2^k$ numbers. The best graphical representation known is of size roughly $2^{2^k}$ {{cite\|HagerupKNR-98,KhanR-14}}.
		+
		+	* A deterministic data structure for $(1+\varepsilon)$-approximating any multicommodity flow on a set of $k$ given terminals in $G$. There is no known graphical representation for this, whose size depends on $k$ and $\varepsilon$, but not on $G$ {{cite\|AndoniGK-14}}.

← Older revision		Revision as of 14:11, 15 January 2016
Line 11:		Line 11:

	Thus for this problem, a very space-efficient data structure (perhaps even the best one) is itself a graph $G'$, and it encodes the desired values in a natural manner, just compute the same function (min $st$-cut) on $G'$.		Thus for this problem, a very space-efficient data structure (perhaps even the best one) is itself a graph $G'$, and it encodes the desired values in a natural manner, just compute the same function (min $st$-cut) on $G'$.
−	But is this the case for all such functions on graphs, or is there a (natural) case where a potentially complicated data structure outperforms a graphical encoding?	+	But is this the case for all such functions on graphs, or is there a (natural) case where a potentially complicated data structure outperforms a graphical encoding? The question applies both to exact and approximate computations of the function.

@@ Line 4: / Line 4: @@
 |who=Robert Krauthgamer
 }}
-Given an undirected graph $G = (V,E_G)$ with weight function $w_G$, one may wish to design a data structure to store the value of the minimum $s$–$t$ cut, for any $s,t \in V$.
+Suppose we want to design a data structure that stores, for a given edge-weighted (undirected) graph $G = (V,E_G,w_G)$, the values of the minimum $st$-cuts for all $s,t \in V$.
-A naive method is to construct a table containing the value for each pair, requiring $O(|V|^2)$ space.
+A naive method is to construct a table containing the value for each pair, requiring $O(|V|^2)$ space (machine words).
 Alternatively, one may construct a Gomory–Hu tree {{cite|GomoryH-61}}.
-This is an undirected tree $T = (V,E_T)$ with weight function $w_T$, such that the minimum $s$–$t$ cut values from $G$ are preserved.
+This is a tree $T = (V,E_T,w_T)$, in which the minimum $st$-cut values are equal to those in $G$.
 Since $T$ is a tree, it requires only $O(|V|)$ space.
-For this problem, it turns out the most space-efficient data structure is a graph which preserves the value of the function we wish to query.
+Thus for this problem, a very space-efficient data structure (perhaps even the best one) is itself a graph $G'$, and it encodes the desired values in a natural manner, just compute the same function (min $st$-cut) on $G'$.
-But is this the case for all such functions on graphs, or is there a (natural) case where another—potentially complicated—data structure could out-perform a graph?
+But is this the case for all such functions on graphs, or is there a (natural) case where a potentially complicated data structure outperforms a graphical encoding?

← Older revision	Revision as of 18:40, 18 January 2016
(No difference)

← Older revision		Revision as of 18:09, 12 January 2016
Line 11:		Line 11:

	For this problem, it turns out the most space-efficient data structure is a graph which preserves the value of the function we wish to query.		For this problem, it turns out the most space-efficient data structure is a graph which preserves the value of the function we wish to query.
−	But is this the case for all such functions on graphs, or is there a case where another (potentially complicated) data structure could out-perform a graph?	+	But is this the case for all such functions on graphs, or is there a (natural) case where another — potentially complicated — data structure could out-perform a graph?