Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/98033
Title: Efficient distributed approximation algorithms via probabilistic tree embeddings
Authors: Khan, Maleq.
Kuhn, Fabian.
Malkhi, Dahlia.
Pandurangan, Gopal.
Talwar, Kunal.
Issue Date: 2012
Source: Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G., & Talwar, K. (2012). Efficient distributed approximation algorithms via probabilistic tree embeddings. Distributed Computing, 25(3), 189-205.
Series/Report no.: Distributed computing
Abstract: We present a uniform approach to design efficient distributed approximation algorithms for various fundamental network optimization problems. Our approach is randomized and based on a probabilistic tree embedding due to Fakcharoenphol et al. (J Comput Syst Sci 69(3):485–497, 2004) (FRT embedding). We show how to efficiently compute an (implicit) FRT embedding in a decentralized manner and how to use the embedding to obtain efficient expected O(log n)-approximate distributed algorithms for various problems, in particular the generalized Steiner forest problem (including the minimum Steiner tree problem), the minimum routing cost spanning tree problem, and the k-source shortest paths problem. The distributed construction of the FRT embedding is based on the computation of least elements (LE) lists, a distributed data structure that is of independent interest. Assuming a global order on the nodes of a network, the LE-list of a node stores the smallest node (w.r.t. the given order) within every distance d (cf. Cohen in J Comput Syst Sci 55(3):441–453, 1997, Cohen and Kaplan in J Comput Syst Sci 73(3):265–288, 2007). Assuming a random order on the nodes, we give a distributed algorithm for computing LE-lists on a weighted graph with time complexity O(S log n), where S is a graph parameter called the shortest path diameter which can be considered the weighted counterpart of the diameter D of the graph. For unweighted graphs, our LE-lists computation has asymptotically optimal time complexity of O(D). As a byproduct, we get an improved synchronous leader election algorithm for general networks that is both time-optimal and almost message-optimal with high probability.
URI: https://hdl.handle.net/10356/98033
http://hdl.handle.net/10220/13238
DOI: http://dx.doi.org/10.1007/s00446-012-0157-9
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.