View in EDS

DISTRIBUTED EXACT WEIGHTED ALL-PAIRS SHORTEST PATHS IN RANDOMIZED NEAR-LINEAR TIME.

Saved in:
Bibliographic Details
Title: DISTRIBUTED EXACT WEIGHTED ALL-PAIRS SHORTEST PATHS IN RANDOMIZED NEAR-LINEAR TIME.
Authors: BERNSTEIN, AARON1 bernstei@gmail.com, NANONGKAI, DANUPON2 danupon@gmail.com
Source: SIAM Journal on Computing. 2023, Vol. 52 Issue 2, p112-127. 16p.
Subjects: IEEE Computer Society, Polynomial approximation, Directed graphs, Approximation algorithms, Graph algorithms, Distributed algorithms, Problem solving
Geographic Terms: New York (State)
Abstract: Abstract. In the distributed all-pairs shortest paths problem, every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity). The problem admits a (1 + (1))-approximation 9(n)-time algorithm and a nearly tight 12(n) lower bound [D. Nanongkai, STOC'14, ACM, New York, 2014, pp. 565-573; C. Lenzen and B. Patt-Shamir, PODC'15, ACM, New York, 2015, pp. 153-162]. (9, 0 and n hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios (C. Lenzen and D. Peleg, PODC, ACM, New York, 2013, pp. 375-382; S. Holzer and R. Wattenofer, PODC, ACM, New York, 2012, pp. 355-364; D. Peleg, L. Roditty, and E. Tal, ICALP, Springer, Berlin, 2012, pp. 660-672; D. Nanongkai, STOC, ACM, New York, 2014, pp. 565-573-672). For the exact case, Elkin [STOC'17, ACM, New York, 2017, pp. 757-790] presented an 0(n5/3 log2/3 n) time bound, which was later improved to O(n5/4) [C.-C. Huang, D. Nanongkai, T. Saranurak, FOCS'17, IEEE Computer Society, Los Alamitos, CA, 2017, pp. 168-179]. It was shown that any superlinear lower bound (in n) requires a new technique [K. Censor-Hillel, S. Khoury, A. Paz, DISC'17, LIPIcs Leibniz Int. Proc. Inform., Vol. 91, Schloss-Dagstuhl, Wadern, Germany, 2017, 10], but otherwise it remained widely open whether there exists a O(n)-time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) 0(n)-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous 0(n5/4) bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous 0(n5/4) bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in {1, 2, ..., poly(n)}). As far as we know, ours is the first o(n²) algorithm that only requires unidirectional communication. For arbitrary weights, the previous state-of-the-art required 0(n4/3) time [U. Agarwal and V. Ramachandran, IPDPS 2019, IEEE Computer Society, Los Alamitos, CA, 2019, and SPAA 2020, ACM, New York, 2020, pp. 11-21]. Our algorithm is extremely simple and relies on a new technique called random filtered broadcast. Given any sets of nodes A, B C V and assuming that every b E B knows all distances from nodes in A, and every node v E V knows all distances from nodes in B, we want every v E V to know DistThroughB (a, v) = minbEB dist(a, b) + dist(b, v) for every a E A. Previous works typically solve this problem by broadcasting all knowledge of every b E B, causing superlinear edge congestion and time. We show a randomized algorithm that can reduce edge congestions and thus solve this problem in 0(n) expected time. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 163957844
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: DISTRIBUTED EXACT WEIGHTED ALL-PAIRS SHORTEST PATHS IN RANDOMIZED NEAR-LINEAR TIME.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22BERNSTEIN%2C+AARON%22">BERNSTEIN, AARON</searchLink><relatesTo>1</relatesTo><i> bernstei@gmail.com</i><br /><searchLink fieldCode="AR" term="%22NANONGKAI%2C+DANUPON%22">NANONGKAI, DANUPON</searchLink><relatesTo>2</relatesTo><i> danupon@gmail.com</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Computing%22">SIAM Journal on Computing</searchLink>. 2023, Vol. 52 Issue 2, p112-127. 16p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22IEEE+Computer+Society%22">IEEE Computer Society</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomial+approximation%22">Polynomial approximation</searchLink><br /><searchLink fieldCode="DE" term="%22Directed+graphs%22">Directed graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Approximation+algorithms%22">Approximation algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+algorithms%22">Graph algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed+algorithms%22">Distributed algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+solving%22">Problem solving</searchLink>
– Name: SubjectGeographic
  Label: Geographic Terms
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22New+York+%28State%29%22">New York (State)</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Abstract. In the distributed all-pairs shortest paths problem, every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity). The problem admits a (1 + (1))-approximation 9(n)-time algorithm and a nearly tight 12(n) lower bound [D. Nanongkai, STOC'14, ACM, New York, 2014, pp. 565-573; C. Lenzen and B. Patt-Shamir, PODC'15, ACM, New York, 2015, pp. 153-162]. (9, 0 and n hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios (C. Lenzen and D. Peleg, PODC, ACM, New York, 2013, pp. 375-382; S. Holzer and R. Wattenofer, PODC, ACM, New York, 2012, pp. 355-364; D. Peleg, L. Roditty, and E. Tal, ICALP, Springer, Berlin, 2012, pp. 660-672; D. Nanongkai, STOC, ACM, New York, 2014, pp. 565-573-672). For the exact case, Elkin [STOC'17, ACM, New York, 2017, pp. 757-790] presented an 0(n5/3 log2/3 n) time bound, which was later improved to O(n5/4) [C.-C. Huang, D. Nanongkai, T. Saranurak, FOCS'17, IEEE Computer Society, Los Alamitos, CA, 2017, pp. 168-179]. It was shown that any superlinear lower bound (in n) requires a new technique [K. Censor-Hillel, S. Khoury, A. Paz, DISC'17, LIPIcs Leibniz Int. Proc. Inform., Vol. 91, Schloss-Dagstuhl, Wadern, Germany, 2017, 10], but otherwise it remained widely open whether there exists a O(n)-time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) 0(n)-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous 0(n5/4) bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous 0(n5/4) bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in {1, 2, ..., poly(n)}). As far as we know, ours is the first o(n²) algorithm that only requires unidirectional communication. For arbitrary weights, the previous state-of-the-art required 0(n4/3) time [U. Agarwal and V. Ramachandran, IPDPS 2019, IEEE Computer Society, Los Alamitos, CA, 2019, and SPAA 2020, ACM, New York, 2020, pp. 11-21]. Our algorithm is extremely simple and relies on a new technique called random filtered broadcast. Given any sets of nodes A, B C V and assuming that every b E B knows all distances from nodes in A, and every node v E V knows all distances from nodes in B, we want every v E V to know DistThroughB (a, v) = minbEB dist(a, b) + dist(b, v) for every a E A. Previous works typically solve this problem by broadcasting all knowledge of every b E B, causing superlinear edge congestion and time. We show a randomized algorithm that can reduce edge congestions and thus solve this problem in 0(n) expected time. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=163957844
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/20M1312782
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 16
        StartPage: 112
    Subjects:
      – SubjectFull: IEEE Computer Society
        Type: general
      – SubjectFull: Polynomial approximation
        Type: general
      – SubjectFull: Directed graphs
        Type: general
      – SubjectFull: Approximation algorithms
        Type: general
      – SubjectFull: Graph algorithms
        Type: general
      – SubjectFull: Distributed algorithms
        Type: general
      – SubjectFull: Problem solving
        Type: general
      – SubjectFull: New York (State)
        Type: general
    Titles:
      – TitleFull: DISTRIBUTED EXACT WEIGHTED ALL-PAIRS SHORTEST PATHS IN RANDOMIZED NEAR-LINEAR TIME.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: BERNSTEIN, AARON
      – PersonEntity:
          Name:
            NameFull: NANONGKAI, DANUPON
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 03
              Text: 2023
              Type: published
              Y: 2023
          Identifiers:
            – Type: issn-print
              Value: 00975397
          Numbering:
            – Type: volume
              Value: 52
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: SIAM Journal on Computing
              Type: main
ResultId 1