CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt169",{id:"formSmash:upper:j_idt169",widgetVar:"widget_formSmash_upper_j_idt169",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt175_j_idt177",{id:"formSmash:upper:j_idt175:j_idt177",widgetVar:"widget_formSmash_upper_j_idt175_j_idt177",target:"formSmash:upper:j_idt175:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Distributed exact weighted all-pairs shortest paths in near-linear timePrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
2019 (English)In: Proceeding STOC 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery (ACM), 2019, p. 334-342Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Association for Computing Machinery (ACM), 2019. p. 334-342
##### Series

Proceedings of the Annual ACM Symposium on Theory of Computing, ISSN 0737-8017
##### Keywords [en]

All-pairs shortest paths, CONGEST, Distributed computing, Graph algorithms
##### National Category

Computer and Information Sciences
##### Identifiers

URN: urn:nbn:se:kth:diva-262620DOI: 10.1145/3313276.3316326Scopus ID: 2-s2.0-85068760591ISBN: 9781450367059 (print)OAI: oai:DiVA.org:kth-262620DiVA, id: diva2:1365245
##### Conference

51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019; Phoenix; United States; 23 June 2019 through 26 June 2019
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt721",{id:"formSmash:j_idt721",widgetVar:"widget_formSmash_j_idt721",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt727",{id:"formSmash:j_idt727",widgetVar:"widget_formSmash_j_idt727",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt748",{id:"formSmash:j_idt748",widgetVar:"widget_formSmash_j_idt748",multiple:true});
##### Note

In the distributed all-pairs shortest paths problem (APSP), 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 (1 + o(1))-approximation Θ (n)time algorithm and a nearly-tight Ω (n) lower bound [Nanongkai, STOC’14; Lenzen and Patt-Shamir PODC’15]. For the exact case, Elkin [STOC’17] presented an O(n5/3 log2/3 n) time bound, which was later improved to Õ(n5/4) in [Huang, Nanongkai, Saranurak FOCS’17]. It was shown that any super-linear lower bound (in n) requires a new technique [Censor-Hillel, Khoury, Paz, DISC’17], but otherwise it remained widely open whether there exists a Õ(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) Õ(n)-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous Õ(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 Õ(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))). The previously best algorithm for this more difficult setting required Õ(n3/2) time [Agarwal and Ramachandran, ArXiv’18] (this can be improved to Õ(n4/3) if one allows bidirectional communication). Our algorithm is extremely simple and relies on a new technique called Random Filtered Broadcast. Given any sets of nodes A, B ⊆ V and assuming that every b ∈ B knows all distances from nodes in A, and every node v ∈ V knows all distances from nodes in B, we want every v ∈ V to know DistThroughB(a,v) = minb∈B dist(a,b) + dist(b,v) for every a ∈ A. Previous works typically solve this problem by broadcasting all knowledge of every b ∈ B, causing super-linear edge congestion and time. We show a randomized algorithm that can reduce edge congestions and thus solve this problem in Õ(n) expected time.

QC 20191024

Available from: 2019-10-24 Created: 2019-10-24 Last updated: 2019-10-24Bibliographically approved
doi
isbn
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1844",{id:"formSmash:j_idt1844",widgetVar:"widget_formSmash_j_idt1844",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1897",{id:"formSmash:lower:j_idt1897",widgetVar:"widget_formSmash_lower_j_idt1897",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1898_j_idt1900",{id:"formSmash:lower:j_idt1898:j_idt1900",widgetVar:"widget_formSmash_lower_j_idt1898_j_idt1900",target:"formSmash:lower:j_idt1898:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});