A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs

Debarati Das; Maximilian Probst Gutenberg; Christian Wulff-Nilsen

doi:10.1137/1.9781611977073.138

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs

Debarati Das^*, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

^*Corresponding author af dette arbejde

Algorithms and Complexity

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

7 Citationer (Scopus)

21 Downloads (Pure)

Abstract

In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph G undergoes a sequence of edge weight updates and the goal is to maintain a data structure on G, that can quickly answer distance queries between any two vertices x,y ? V(G). The currently best algorithms [FOCS'01, SODA'05] for this problem require Õ(n2/3) worst-case update and query time, while conditional lower bounds [FOCS'16] show that either update or query time is needed1. In this article, we present the first algorithm with near-optimal worst-case update and query time for the offline setting, where the update sequence is given initially. This result is obtained by giving the first offline dynamic algorithm for maintaining dense distance graphs (DDGs) faster than recomputing from scratch after each update. Further, we also present an online algorithm for the incremental APSP problem with worst-case update/query time. This allows us to reduce the online dynamic APSP problem to the online decremental APSP problem, which constitutes partial progress even for the online version of this notorious problem.

Originalsprog	Engelsk
Titel	ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Forlag	Association for Computing Machinery, Inc.
Publikationsdato	2022
Sider	3482-3495
ISBN (Elektronisk)	9781611977073
DOI	https://doi.org/10.1137/1.9781611977073.138
Status	Udgivet - 2022
Begivenhed	33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, USA Varighed: 9 jan. 2022 → 12 jan. 2022

Konference

Konference	33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Land/Område	USA
By	Alexander
Periode	09/01/2022 → 12/01/2022

Bibliografisk note

Funding Information:
∗University of Copenhagen, Denmark, [email protected]. †ETH Zurich, Switzerland, [email protected]. Supported by Rasmus Kyng’s Start-up Grant at ETH. Work done while at BARC, supported by Thorup’s Investigator Grant No. 16582. ‡University of Copenhagen, Denmark, [email protected]. The author is supported by the Starting Grant 7027-00050B from the Independent Research Fund Denmark under the Sapere Aude research career programme. 1We use Õ and Ω˜-notations to hide poly-logarithmic factors in n.

Publisher Copyright:
Copyright © 2022 by SIAM.

Adgang til dokumentet

10.1137/1.9781611977073.138Licens: Ikke-specificeret

FulltextLicens: Ikke-specificeret

Andre filer og links

Link to publication in Scopus

Citationsformater

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs. / Das, Debarati; Gutenberg, Maximilian Probst; Wulff-Nilsen, Christian.
ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. Association for Computing Machinery, Inc., 2022. s. 3482-3495.

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Das, D, Gutenberg, MP & Wulff-Nilsen, C 2022, A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs. i ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. Association for Computing Machinery, Inc., s. 3482-3495, 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Alexander, USA, 09/01/2022. https://doi.org/10.1137/1.9781611977073.138

@inproceedings{7039e3ce26e9419aa80282d4d41c6c81,

title = "A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs",

abstract = "In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph G undergoes a sequence of edge weight updates and the goal is to maintain a data structure on G, that can quickly answer distance queries between any two vertices x,y ? V(G). The currently best algorithms [FOCS'01, SODA'05] for this problem require {\~O}(n2/3) worst-case update and query time, while conditional lower bounds [FOCS'16] show that either update or query time is needed1. In this article, we present the first algorithm with near-optimal worst-case update and query time for the offline setting, where the update sequence is given initially. This result is obtained by giving the first offline dynamic algorithm for maintaining dense distance graphs (DDGs) faster than recomputing from scratch after each update. Further, we also present an online algorithm for the incremental APSP problem with worst-case update/query time. This allows us to reduce the online dynamic APSP problem to the online decremental APSP problem, which constitutes partial progress even for the online version of this notorious problem. ",

author = "Debarati Das and Gutenberg, {Maximilian Probst} and Christian Wulff-Nilsen",

note = "Publisher Copyright: Copyright {\textcopyright} 2022 by SIAM.; 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 ; Conference date: 09-01-2022 Through 12-01-2022",

year = "2022",

doi = "10.1137/1.9781611977073.138",

language = "English",

pages = "3482--3495",

booktitle = "ACM-SIAM Symposium on Discrete Algorithms, SODA 2022",

publisher = "Association for Computing Machinery, Inc.",

}

TY - GEN

T1 - A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs

AU - Das, Debarati

AU - Gutenberg, Maximilian Probst

AU - Wulff-Nilsen, Christian

PY - 2022

Y1 - 2022

N2 - In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph G undergoes a sequence of edge weight updates and the goal is to maintain a data structure on G, that can quickly answer distance queries between any two vertices x,y ? V(G). The currently best algorithms [FOCS'01, SODA'05] for this problem require Õ(n2/3) worst-case update and query time, while conditional lower bounds [FOCS'16] show that either update or query time is needed1. In this article, we present the first algorithm with near-optimal worst-case update and query time for the offline setting, where the update sequence is given initially. This result is obtained by giving the first offline dynamic algorithm for maintaining dense distance graphs (DDGs) faster than recomputing from scratch after each update. Further, we also present an online algorithm for the incremental APSP problem with worst-case update/query time. This allows us to reduce the online dynamic APSP problem to the online decremental APSP problem, which constitutes partial progress even for the online version of this notorious problem.

AB - In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph G undergoes a sequence of edge weight updates and the goal is to maintain a data structure on G, that can quickly answer distance queries between any two vertices x,y ? V(G). The currently best algorithms [FOCS'01, SODA'05] for this problem require Õ(n2/3) worst-case update and query time, while conditional lower bounds [FOCS'16] show that either update or query time is needed1. In this article, we present the first algorithm with near-optimal worst-case update and query time for the offline setting, where the update sequence is given initially. This result is obtained by giving the first offline dynamic algorithm for maintaining dense distance graphs (DDGs) faster than recomputing from scratch after each update. Further, we also present an online algorithm for the incremental APSP problem with worst-case update/query time. This allows us to reduce the online dynamic APSP problem to the online decremental APSP problem, which constitutes partial progress even for the online version of this notorious problem.

UR - http://www.scopus.com/inward/record.url?scp=85127299237&partnerID=8YFLogxK

U2 - 10.1137/1.9781611977073.138

DO - 10.1137/1.9781611977073.138

M3 - Article in proceedings

AN - SCOPUS:85127299237

SP - 3482

EP - 3495

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

PB - Association for Computing Machinery, Inc.

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Y2 - 9 January 2022 through 12 January 2022

ER -