NDLI: Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

Content Provider	IEEE Xplore Digital Library
Author	Henzinger, M. Krinninger, S. Nanongkai, D.
Copyright Year	2013
Description	Author affiliation: Div. of Math. Sci., Nanyang Technol. Univ., Singapore, Singapore (Nanongkai, D.) \|\| Fac. of Comput. Sci., Univ. of Vienna, Vienna, Austria (Henzinger, M.; Krinninger, S.)
Abstract	We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of $O(mn^{2})$ and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of $Ȏ(n^{5/2})$ and constant query time that has an additive error of two in addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time when m = $Ω(n^{3/2}).$ Note that the additive error is unavoidable since, even in the static case, an $O(n^{3-δ})-time$ (a so-called truly sub cubic) combinatorial algorithm with 1 + ϵ multiplicative error cannot have an additive error less than 2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 + ϵ)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n5/2+O(1√(log n))) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + ϵ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper. In order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator. (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.
Starting Page	538
Ending Page	547
File Size	256759
Page Count	10
File Format	PDF
ISBN	9780769551357
ISSN	02725428
DOI	10.1109/FOCS.2013.64
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-10-26
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Approximation algorithms Approximation methods Heuristic algorithms Additives Algorithm design and analysis Educational institutions Computer science emulator dynamic graph algorithms all-pairs shortest paths derandomization
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization (2013)

Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time

Dynamic approximate all-pairs shortest paths in undirected graphs

All-Pairs Shortest Paths in O(n²) Time with High Probability

All-Pairs Almost Shortest Paths

Minimizing Communication in All-Pairs Shortest Paths

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

Similar Documents

Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization (2013)

Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time

Dynamic approximate all-pairs shortest paths in undirected graphs

All-Pairs Shortest Paths in O(n²) Time with High Probability

All-Pairs Almost Shortest Paths

Minimizing Communication in All-Pairs Shortest Paths

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization