Open Problems:14 - Revision history

Krzysztof Onak: Fixing a typo.

2016-09-25T22:17:24Z

Fixing a typo.

Krzysztof Onak at 21:13, 26 June 2013

2013-06-26T21:13:47Z

Krzysztof Onak: updating header

2013-03-07T01:41:14Z

updating header

Krzysztof Onak at 05:08, 16 November 2012

2012-11-16T05:08:30Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak at 19:35, 20 October 2012

2012-10-20T19:35:29Z

New page

{{DISPLAYTITLE:Problem 14: Graph Distances}}
{{Infobox
|label1 = Proposed by
|data1 = Andrew McGregor
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/14
}}
Given a stream of edges defining a graph $G$, how well can we estimate $d_G(u,v)$, the length of the shortest path between two nodes $u$ and $v$? Progress that has been made on this problem is based on constructing ''spanners'' {{cite|FeigenbaumKMSZ-05|FeigenbaumKMSZ-05a|ElkinZ-06|Baswana-06|Elkin-06}} where subgraph $H$ of $G$ is an $(\alpha,\beta)$-spanner
for $G$ if
\[\forall x,y \in V, \ d_G(x,y)\le d_H(x,y) \le \alpha \cdot d_G(x,y)+\beta \enspace .\]
Clearly, an $(\alpha,\beta)$-spanner gives an $\alpha+\beta/d_G(u,v)$ approximation to $d_G(u,v)$.
Since a spanner is constructed independently of $u$ and $v$ it is perhaps surprising that this approach gives nearly optimal results for approximating $d_G(u,v)$ in a single pass {{cite|FeigenbaumKMSZ-05}}. It is unclear whether there is a better approach for multiple pass algorithms. Clearly, $d_G(u,v)$ can be computed exactly in $d_G(u,v)$ passes but for $d_G(u,v)$ large this is infeasible. Can we do better? For example, how well can $d_G(u,v)$ be approximated in $O(\log n)$ passes? What if the edges arrived in random order?

← Older revision		Revision as of 22:17, 25 September 2016
Line 10:		Line 10:

	== Update ==		== Update ==
−	Guruswami and Onak {{cite\|GuruswamiO-13}} showed that checking if $d_G(u,v) \le 2(p+1)$ in $p$ passes, where $p = O\left(\frac{\log n}{\log\log n}\right)$, requires $\Omega\left(\frac{n^{1+1/(2p+p)}}{p^{20}\log^{3/2}n}\right)$ bits of space.	+	Guruswami and Onak {{cite\|GuruswamiO-13}} showed that checking if $d_G(u,v) \le 2(p+1)$ in $p$ passes, where $p = O\left(\frac{\log n}{\log\log n}\right)$, requires $\Omega\left(\frac{n^{1+1/(2p+2)}}{p^{20}\log^{3/2}n}\right)$ bits of space.

← Older revision		Revision as of 21:13, 26 June 2013
Line 8:		Line 8:
	Clearly, an $(\alpha,\beta)$-spanner gives an $\alpha+\beta/d_G(u,v)$ approximation to $d_G(u,v)$.		Clearly, an $(\alpha,\beta)$-spanner gives an $\alpha+\beta/d_G(u,v)$ approximation to $d_G(u,v)$.
	Since a spanner is constructed independently of $u$ and $v$ it is perhaps surprising that this approach gives nearly optimal results for approximating $d_G(u,v)$ in a single pass {{cite\|FeigenbaumKMSZ-05}}. It is unclear whether there is a better approach for multiple pass algorithms. Clearly, $d_G(u,v)$ can be computed exactly in $d_G(u,v)$ passes but for $d_G(u,v)$ large this is infeasible. Can we do better? For example, how well can $d_G(u,v)$ be approximated in $O(\log n)$ passes? What if the edges arrived in random order?		Since a spanner is constructed independently of $u$ and $v$ it is perhaps surprising that this approach gives nearly optimal results for approximating $d_G(u,v)$ in a single pass {{cite\|FeigenbaumKMSZ-05}}. It is unclear whether there is a better approach for multiple pass algorithms. Clearly, $d_G(u,v)$ can be computed exactly in $d_G(u,v)$ passes but for $d_G(u,v)$ large this is infeasible. Can we do better? For example, how well can $d_G(u,v)$ be approximated in $O(\log n)$ passes? What if the edges arrived in random order?
		+
		+	== Update ==
		+	Guruswami and Onak {{cite\|GuruswamiO-13}} showed that checking if $d_G(u,v) \le 2(p+1)$ in $p$ passes, where $p = O\left(\frac{\log n}{\log\log n}\right)$, requires $\Omega\left(\frac{n^{1+1/(2p+p)}}{p^{20}\log^{3/2}n}\right)$ bits of space.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Andrew McGregor

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 14: Graph Distances}}
+{{Header
-{{Infobox
+|title=Graph Distances
-|label1 = Proposed by
+|source=kanpur06
-|data1 = Andrew McGregor
+|who=Andrew McGregor
 }}
 Given a stream of edges defining a graph $G$, how well can we estimate $d_G(u,v)$, the length of the shortest path between two nodes $u$ and $v$? Progress that has been made on this problem is based on constructing ''spanners'' {{cite|FeigenbaumKMSZ-05|FeigenbaumKMSZ-05a|ElkinZ-06|Baswana-06|Elkin-06}} where subgraph $H$ of $G$ is an $(\alpha,\beta)$-spanner

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)