Difference between revisions of "Open Problems:14"
m (1 revision) |
(Fixing a typo.) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |source=kanpur06 | |
| − | | | + | |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 | 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 | ||
| Line 13: | 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+2)}}{p^{20}\log^{3/2}n}\right)$ bits of space. | ||
Latest revision as of 22:17, 25 September 2016
| Suggested by | Andrew McGregor |
|---|---|
| Source | Kanpur 2006 |
| Short link | https://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 [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 [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[edit]
Guruswami and Onak [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.
