Linear Time Augmenting Paths Algorithm for Radius Optimization in Metric Space
The research presents a linear time augmenting paths algorithm for optimizing radius in a metric space. It addresses finding the center and radius of a given path graph, as well as the optimally augmenting path problem. Related work on minimizing diameter in different scenarios is also discussed.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
A A Linear Linear- -Time Augmenting Augmenting Paths Time Algorithm for Algorithm for Radius Paths in a in a Metric Space Radius- -Optimally Optimally Metric Space Christopher Johnson and Haitao Wang Utah State University WADS 2019, Edmonton, Canada
A path graph in a metric space A path graph in a metric space P: a path graph of n vertices v1, v2, , vn Assume all vertices are in a metric space |vivj|: the distance of every two vertices viand vj Triangle inequality: |vivj| + |vjvk| |vivk|, for any three vertices vi, vj, vk What is the center of P? A point c in P that minimizes the maximum distance in P from c to all vertices of P A point c whose distances in P from v1and vnare equal Maybe in the interior of an edge What is the radius of P? The longest distance from c to all vertices The distance from c to v1or vn Half of the total length of P |v2v4| + |v4v6| |v2v6| v7 v1 v2 v6 c v3 v5 v4
The radius The radius- -optimally augmenting path problem optimally augmenting path problem Add an edge e(vi,vj) to connect two vertices vi and vj, so that the radius of the new graph is minimized The length of e(vi,vj) is |vivj|, which can be obtained in O(1) time Where is the center and what is the radius of the new graph? Previous work None A straightforward solution Try all O(n2) possible new edges Our result O(n) time v7 c v1 v2 v6 c v3 v5 v4
Related work Related work minimizing the diameter minimizing the diameter O(n log3 n) time, Gro e et al., 2015 O(n log n) time, Wang, 2017 If P is in the Euclidean plane R2 O(n) time, De Carufel et al., 2016 to minimize the continuous diameter, defined with respect to all points of the graph, not just the vertices For a geometric tree T of n vertices embedded in the Euclidean plane R2 O(n log n) time for continuous diameter, De Carufel et al., 2017 For a tree T in a metric space, minimize the discrete diameter O(n2 log n) time, Gro e et al., 2016 O(n log n) time, Bil , 2018 discrete diameter
Related work Related work minimizing the diameter (cont.) minimizing the diameter (cont.) For a general tree T, minimize the discrete diameter O(n2 log3 n) time, Oh and Ahn, 2016 O(n2) time, Bil , 2018 optimal For a general tree T, minimize the continuous diameter O(n2 log3 n) time, Oh and Ahn, 2016
Potential applications Potential applications Suppose there is a highway that connects several cities (or a similar network) We want to build a facility (such as a supply center) along the highway to provide certain service for all these cities In order to reduce the transportation time, we plan to build a new highway connecting two cities such that the radius (i.e., the maximum distance from the cities to the facility located at the center) is as small as possible v7 v1 v2 v6 v3 v5 v4
The diameter vs. the radius The diameter vs. the radius The radius of P is equal to its diameter divided by two But this is usually not true if a new edge is added Example: Assume a new edge connects v1 and vn Assume all edges have length 1 and n is even The diameter is n/2 The radius is n/2 1/2 very close to the diameter v8 c v7 v1 v2 v6 v3 v5 v4
Overview of our approach Overview of our approach Consider all possible configurations of an optimal solution, determined by the location of the center c the two farthest vertices the shortest paths from c to the two farthest vertices For each configuration, there must be two farthest vertices such that the union of their shortest paths to c contains c in the interior c c vn v1 vj vn v1 vj vi vi c c vn v1 vj vn v1 vj vi vi
Other configurations Other configurations c c vn v1 vj vn v1 vi vj vi c c vn v1 vj vn v1 vj vi vi c c vn v1 vj vn v1 vj vi vi vn v1 vj vn v1 vi c vj c vi
Overview of our approach Overview of our approach A constant number of configurations For each configuration, compute in O(n) time a candidate solution (a center and radius) The best solution in the configuration If an optimal solution of the problem belongs to that configuration, then our solution is also an optimal solution Among all O(1) candidate solutions, return the one with minimum radius Total time: O(n)
Our algorithm Our algorithm Configuration: the center c is in P between v1 and vi v1 is a farthest vertex The radius is equal to the distance in P from c to v1 The other farthest vertex is between vi and vn c c vn v1 vj vi vn v1 vj vi c c vn v1 vn v1 vj vj vi vi c vn v1 vj vi
Configuration: c is in P between v Configuration: c is in P between v1 1 and v and vi i R: the optimal radius G(i,j): the new graph with the new edge connecting vi and vj dP(u,v): the distance between two vertices u and v in P dG(i,j)(u,v): the distance between two vertices u and v in G(i,j) vb: the other farthest vertex of c Observations: R = dP(v1,c) = dP(c,vi) + dG(i,j)(vi,vb) 2R = dP(v1,vi) + dG(i,j)(vi,vb) dG(i,j)(vi,vb) = maxi k ndG(i,j)(vi,vk) c vb vn v1 vj vi
Configuration: c is in P between v Configuration: c is in P between v1 1 and v and vi i 2R = dP(v1,vi) + dG(i,j)(vi,vb) dG(i,j)(vi,vb) = maxi k ndG(i,j)(vi,vk) Among all indices in [i,n], j minimizes maxi k ndG(i,j)(vi,vk) Define i = mini j nmaxi k ndG(i,j)(vi,vk) dG(i,j)(vi,vb) = i 2R = dP(v1,vi) + i Algorithm: Compute i for all i = 1, 2, , n O(n) time, based on some monotonicity properties and the triangle inequality Among all indices i with dP(v1,vi) i, return the one minimizing dP(v1,vi) + i c vb vn v1 vj vi
Configuration: c is in P between v Configuration: c is in P between v1 1 and v and vi i c vn v1 vj vi c c vn v1 vn v1 vj vj vi vi
Configuration: c is on the new edge Configuration: c is on the new edge c c vn v1 vj vn v1 vj vi vi c c vn v1 vj vn v1 vj vi vi
Case 1: v Case 1: v1 1 and and v vn n are the two farthest vertices are the two farthest vertices Observation: Let k be the smallest index with dP(v1,vi) < dP(vi,vk), and such k must exist in [i,j] Given any i, k is uniquely determined j is the largest index with dP(vk,vj) dP(vj,vn) j is uniquely determined by k Given any i, k and j are uniquely determined Algorithm: Compute such indices k and j for all i = 1, 2, , n c vn vj v1 vk vi O(n) time, based on some monotonicity properties: as i increases, both k and j increases Define the candidate radius: r = (dP(v1,vi) + |vivj| + dP(vj,vn))/2 Among all indices i with dP(v1,vi) < r and dP(vj,vn) < r, return the one of minimum r
Case 2: v Case 2: v1 1 is a farthest vertex and another one is is a farthest vertex and another one is between v between vi i and and v vj j Observation: Let k be the smallest index with dP(v1,vi) < dP(vi,vk), and such k must exist in [i,j] Given any i, k is uniquely determined k = b j is the smallest index with dP(vk,vj) > dP(vj,vn) j is uniquely determined by k Given any i, k and j are uniquely determined Algorithm: Compute such indices k and j for all i = 1, 2, , n c vkvk=vb vb v1 vj vn vi O(n) time, based on some monotonicity properties Define: r = (dP(v1,vi) + |vivj| + dP(vj,vk))/2 Among all indices i with dP(v1,vi) < r and dP(vj,vk) < r, return the one of minimum r
Case 3: both farthest vertices are between v Case 3: both farthest vertices are between vi i and and v vj j Observation: b = a+1 i is the largest index in [1,a] with dP(v1,vi) < dP(vi,va) Given any a, i is uniquely determined j is the smallest index in [b,n] with dP(vj,vn) < dP(vb,vj) j is uniquely determined by b Given a, the indices i and j are uniquely determined Algorithm: Compute such indices i and j for all a = 1, 2, , n - 1 c v1 vj vn vi vb va O(n) time, based on some monotonicity properties Define: r = (dP(vi,va) + |vivj| + dP(vj,va+1))/2 Among all indices i with dP(vi,va) < r and dP(va+1,vj) < r, return the one of minimum r
Conclusions Conclusions A constant number of configurations For each configuration, compute in O(n) time the best solution as a candidate (a candidate center and a candidate radius) If an optimal solution of the problem belongs to that configuration, then our solution is also an optimal solution The solution is also feasible If we place a point c at the candidate center, then the longest distance from c to all vertices is equal to the candidate radius Among all O(1) candidate solutions, return the one with minimum radius Total time: O(n)
Thank you for your attention! Thank you for your attention! Questions?
