Mastering Matlab for Efficient Data Processing
Enhance your skills in Matlab with a comprehensive guide covering basic commands, concatenation, data types, advanced classes, vectorization, logical indexing, distributed processing, complex indexing techniques, and more. Learn how to optimize matrix calculations, utilize distributed processing functions, and work with classes and inheritance in Matlab. Improve your code efficiency and performance for data analysis and manipulation tasks.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Maintaining Exact Distances under Multiple Edge Failures Ran Duan Tsinghua Hanlin Ren Oxford STOC 22 1 / 16
The Problem Problem: given a graph, deal with failures. Example: Query ?,?,? = shortest path from ? to ? that avoids ? source vertex target vertex failed edge optimal path 2 / 16
How Hard Is the Problem? Easiest case: 1 failure Query ?,?,? = shortest path from ? to ? that avoids ? ? is either a failed edge or a failed vertex A lot of literature [DTCR 08] [BK 08] [BK 09] [WY 10] [GW 12] [DZ 17] [CC 20] [R 20] [GR 21] Highly nontrivial solutions with ? ?2size and ? 1 query time Both parameters are optimal! 3 / 16
How Hard Is the Problem? 2 failures: considerably more complicated [DP 09] Space complexity: ? ?2, query time: ? log? 4 / 16
Okay, What about More Failures? ? (vertex / edge) failures Previous work can be categorised into two types: Type I Answers weaker queries, e.g., connectivity, reachability, approx distance Query time: poly log?,? fast [PT 07] [DP 10] [DP 16] [CLPR 12] [BGLP 16] [CCFK 17] [DGR 21] [LS 22] Type II Maintains exact distances Query time: ? 1 slow [WY 13] [BS 19] 5 / 16
Lets Focus on Exact Distances ? (vertex / edge) failures, maintain exact distance Na ve solution: enumerate all possible queries Size ? ??+2, query ? 1 [DP 09]: can achieve size ? ??, query ? log? No other results with fast query time known When ? is a constant, want query time to be polylog ? Problem An Easier Problem Is there a 100-failure exact distance oracle with query time polylog ? and size ? ?99? For large constant ?, is there a ?-failure exact distance oracle with query time polylog ? and a reasonable size bound? 6 / 16
Our Results Problem An Easier Problem Is there a 100-failure exact distance oracle with query time polylog ? and size ? ?99? For large constant ?, is there a ?-failure exact distance oracle with query time polylog ? and a reasonable size bound? We show the answer is YES! for undirected graphs and edge failures Main Result: Query time ?? ?, size ? ??4. 7 / 16
A Structural Theorem [ABKCM 02]: Any shortest path under ? edge failures can be decomposed into the concatenation of at most ? + 1 shortest paths (in the original graph) interleaved with at most ? edges. An example where ? = 3 3 interleaving edges 4 shortest paths 8 / 16
A Recursive Approach path? ??,? = shortest path from ? to ? after ? fails rank? ??,? = the number of segments in path? ??,? Structural theorem: rank? ??,? ? + 1 Goal: find any vertex ? that is on path? ??,? , but neither on the first nor on the last segment bad (not on the wanted path) segments = shortest path in the original (failure-free) graph rank? ??,? ,rank? ??,? < rank? ?(?,?) okay okay bad (on the first segment) ? ? bad (on the last segment) 9 / 16
A Recursive Approach Solve ?,?,? If rank? ??,? = 1, return the original shortest path from ? to ? Otherwise, find some ? that is on path? ??,? , but neither on the first nor on the last segment Actually, it suffices to find poly ? vertices such that one of them satisfies the condition! Return Solve ?,?,? concat Solve ?,?,? This path doesn t contain failures Recursion depth = ? ? Time complexity = ?? ? ? ? ? 10 / 16
Finding a Hitting Set Goal: find a hitting set of poly ? vertices, one of which is on path? ??,? , but neither on the first nor on the last segment Today s talk First, find a small set containing some ? path? ??,? Then, a taste of our techniques on how to escape the first/last segments This is actually very simple! Escaping the first/last segments turns out to be the most technical part of our work ? ? ? 11 / 16
Finding a Hitting Set Define ? ?,? = arg?maxdis? ??,? the set of ? edges whose failure maximises the distance from ? to ? Claim: ? ?,? is a good hitting set! Proof by contradiction: Suppose path? ??,? does not go through ? path? ??,? is a valid candidate for dis? ? ?,? Therefore, dis? ??,? = length of path? ??,? dis? ??,? = dis? ? ?,? dis? ??,? dis? ? ?,? Precompute ? ?,? . Query ?,?,? : either dis? ??,? = dis? ? ?,? , or ? ?,? is a good hitting set! 12 / 16
Escaping the First/Last Segment Consider the scenario: we already know vertices ? ,? , on the first/last segment, respectively. They represent our failure to find vertices not on the first/last segment ? ?,?,? ,? = arg?maxdis? ??,? where ? does not intersect path ?,? and path ? ,? Find some hitting vertex ? If ? is not on the first/last segment, we re done! Otherwise, push ? or ? to ? ? ? ? ? ? ? 13 / 16
Escaping the First/Last Segment Question: how many times we need to push down ? ? Trivial upper bound: ? ? ??: the shortest path tree rooted at ? ??? : the subtree of ??, rooted at ? Let ?LCA= LCA of failures in ??? ? ?,?,?LCA,?LCA = arg?maxdis? ??,? where ? does not intersect path ?,?LCA and path ?LCA,? ??? ?LCA ? ? failed edge first segment 14 / 16
Escaping the First/Last Segment Question: how many times we need to push down ? ? Each time push ? to some vertex strictly below ?LCA ? = number of failures in ??? , then ? ?, and each push down strictly decreases ? Only need to push down ? times! This yields a hitting set of size poly ? Space complexity: ? ??4because we need to store ? ?,?,? ,? ??? ?LCA ? ? failed edge first segment 15 / 16
Conclusions & Open Problems The first exact distance oracles supporting multiple edge failures with a reasonable size bound (? ?4) and fast query (? 1 ) time The structural lemma doesn t work for vertex failures Open question 1: vertex failures? Open question 2: faster preprocessing time? Need to compute (or approximate) ? ?,? faster ? ?,? = the set of ? edges whose failure maximises the distance from ? to ? Open question 3: improve the size bound to ? ?2? 16 / 16
Thank you! Questions are welcome!
