{"id":"arxiv:2110.15944","kind":"preprint","title":"Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing","authors":["Goran Zuzic","Gramoz Goranci","Mingquan Ye","Bernhard Haeupler","Xiaorui Sun"],"author_count":5,"year":2021,"published":"2021-10-29","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2110.15944","nct_id":null,"source_url":"https://arxiv.org/abs/2110.15944","archive_url":"https://space-kitty.com/papers/arxiv:2110.15944","updated":"2021-10-29","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2110.15944","abstract":"We provide universally-optimal distributed graph algorithms for $(1+\\varepsilon)$-approximate shortest path problems including shortest-path-tree and transshipment. The universal optimality of our algorithms guarantees that, on any $n$-node network $G$, our algorithm completes in $T \\cdot n^{o(1)}$ rounds whenever a $T$-round algorithm exists for $G$. This includes $D \\cdot n^{o(1)}$-round algorithms for any planar or excluded-minor network. Our algorithms never require more than $(\\sqrt{n} + D) \\cdot n^{o(1)}$ rounds, resulting in the first sub-linear-round distributed algorithm for transshipment. The key technical contribution leading to these results is the first efficient $n^{o(1)}$-competitive linear $\\ell_1$-oblivious routing operator that does not require the use of $\\ell_1$-embeddings. Our construction is simple, solely based on low-diameter decompositions, and -- in contrast to all known constructions -- directly produces an oblivious flow instead of just an approximation of the optimal flow cost. This also has the benefit of simplifying the interaction with Sherman's multiplicative weight framework [SODA'17] in the distributed setting and its subsequent rounding procedures.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}