1 Search Results for "Holzer, Stephan"

Document

DOI: 10.4230/LIPIcs.OPODIS.2015.6

Approximation of Distances and Shortest Paths in the Broadcast Congest Clique

Authors: Stephan Holzer and Nathan Pinsker

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract

We study the broadcast version of the CONGEST-CLIQUE model of distributed computing. This model operates in synchronized rounds; in each round, any node in a network of size n can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in [STOC'14] a randomized (2+o(1))-approximation algorithm to compute all pairs shortest paths (APSP) in time ~{O}(sqrt{n}) on weighted graphs. We complement this result by proving that any randomized (2-o(1))-approximation of APSP and (2-o(1))-approximation of the diameter of a graph takes ~Omega(n) time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a (2-o(1))-approximation of all pairs shortest paths is among the hardest graph-problems in the broadcast-version of the CONGEST-CLIQUE model, as any graph-problem where each node receives a linear amount of input can be solved trivially in linear time in this model. This contrasts a recent (1+o(1))-approximation for APSP that runs in time O(n^{0.15715}) and an exact algorithm for APSP that runs in time ~O(n^{1/3}) in the unicast version of the CONGEST-CLIQUE model, a more powerful variant of the broadcast version. This lower bound in the broadcast CONGEST-CLIQUE model is derived by first establishing a new lower bound for (2-o(1))-approximating the diameter in weighted graphs in the CONGEST model, which is of independent interest. This lower bound is then transferred to the CONGEST-CLIQUE model. On the positive side we provide a deterministic version of Nanongkai's (2+o(1))-approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic source-detection algorithm designed for the CONGEST model.

Cite as

Stephan Holzer and Nathan Pinsker. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{holzer_et_al:LIPIcs.OPODIS.2015.6,
  author =	{Holzer, Stephan and Pinsker, Nathan},
  title =	{{Approximation of Distances and Shortest Paths in the Broadcast Congest Clique}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.6},
  URN =		{urn:nbn:de:0030-drops-65971},
  doi =		{10.4230/LIPIcs.OPODIS.2015.6},
  annote =	{Keywords: distributed computing, distributed algorithms, approximation algorithms}
}

Refine by Author
1 Holzer, Stephan
1 Pinsker, Nathan

Refine by Classification

Refine by Keyword
1 approximation algorithms
1 distributed algorithms
1 distributed computing

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Holzer, Stephan"

Approximation of Distances and Shortest Paths in the Broadcast Congest Clique

Abstract

Cite as

Thanks for your feedback!

Could not send message