The Library
Simple dynamic spanners with near-optimal recourse against an adaptive adversary
Tools
Bhattacharya, Sayan, Saranurak, Thatchaphol and Sukprasert, Pattara (2022) Simple dynamic spanners with near-optimal recourse against an adaptive adversary. In: 30th Annual European Symposium on Algorithms (ESA 2022), Germany, 5-9 Sep 2022. Published in: Leibniz International Proceedings in Informatics (LIPIcs) series, 244 17:1-17:19. ISBN 9783959772471. doi:10.4230/LIPIcs.ESA.2022.17 ISSN 1868-8969.
|
PDF
WRAP-Simple-dynamic-spanners-near-optimal-recourse-adaptive-adversary-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (879Kb) | Preview |
|
PDF
WRAP-Simple-dynamic-spanners-near-optimal-recourse-adaptive-adversary-2022.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (664Kb) |
Official URL: https://doi.org/10.4230/LIPIcs.ESA.2022.17
Abstract
Designing dynamic algorithms against an adaptive adversary whose performance match the ones assuming an oblivious adversary is a major research program in the field of dynamic graph algorithms. One of the prominent examples whose oblivious-vs-adaptive gap remains maximally large is the fully dynamic spanner problem; there exist algorithms assuming an oblivious adversary with near-optimal size-stretch trade-off using only polylog(n) update time [Baswana, Khurana, and Sarkar TALG'12; Forster and Goranci STOC'19; Bernstein, Forster, and Henzinger SODA'20], while against an adaptive adversary, even when we allow infinite time and only count recourse (i.e. the number of edge changes per update in the maintained spanner), all previous algorithms with stretch at most log⁵(n) require at least Ω(n) amortized recourse [Ausiello, Franciosa, and Italiano ESA'05].
In this paper, we completely close this gap with respect to recourse by showing algorithms against an adaptive adversary with near-optimal size-stretch trade-off and recourse. More precisely, for any k ≥ 1, our algorithm maintains a (2k-1)-spanner of size O(n^{1+1/k}log n) with O(log n) amortized recourse, which is optimal in all parameters up to a O(log n) factor. As a step toward algorithms with small update time (not just recourse), we show another algorithm that maintains a 3-spanner of size Õ(n^{1.5}) with polylog(n) amortized recourse and simultaneously Õ(√n) worst-case update time.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computer algorithms, Graph algorithms, Computer programming, Computer science -- Mathematics | ||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) series | ||||||
Publisher: | Schloss Dagstuhl -- Leibniz-Zentrum | ||||||
ISBN: | 9783959772471 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 1 September 2022 | ||||||
Dates: |
|
||||||
Volume: | 244 | ||||||
Page Range: | 17:1-17:19 | ||||||
Article Number: | 17 | ||||||
DOI: | 10.4230/LIPIcs.ESA.2022.17 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 28 July 2022 | ||||||
Date of first compliant Open Access: | 14 October 2022 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 30th Annual European Symposium on Algorithms (ESA 2022) | ||||||
Type of Event: | Other | ||||||
Location of Event: | Germany | ||||||
Date(s) of Event: | 5-9 Sep 2022 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year