Efficient distributed approximation algorithms via probabilistic tree embeddings

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). W...

Full description

Saved in:
Bibliographic Details
Main Authors: Khan, Maleq., Kuhn, Fabian., Malkhi, Dahlia., Pandurangan, Gopal., Talwar, Kunal.
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2013
Online Access:https://hdl.handle.net/10356/98033
http://hdl.handle.net/10220/13238
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-98033
record_format dspace
spelling sg-ntu-dr.10356-980332020-03-07T12:34:43Z Efficient distributed approximation algorithms via probabilistic tree embeddings Khan, Maleq. Kuhn, Fabian. Malkhi, Dahlia. Pandurangan, Gopal. Talwar, Kunal. School of Physical and Mathematical Sciences 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. 2013-08-27T03:31:07Z 2019-12-06T19:49:53Z 2013-08-27T03:31:07Z 2019-12-06T19:49:53Z 2012 2012 Journal Article 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. https://hdl.handle.net/10356/98033 http://hdl.handle.net/10220/13238 10.1007/s00446-012-0157-9 en Distributed computing
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
description 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.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Khan, Maleq.
Kuhn, Fabian.
Malkhi, Dahlia.
Pandurangan, Gopal.
Talwar, Kunal.
format Article
author Khan, Maleq.
Kuhn, Fabian.
Malkhi, Dahlia.
Pandurangan, Gopal.
Talwar, Kunal.
spellingShingle Khan, Maleq.
Kuhn, Fabian.
Malkhi, Dahlia.
Pandurangan, Gopal.
Talwar, Kunal.
Efficient distributed approximation algorithms via probabilistic tree embeddings
author_sort Khan, Maleq.
title Efficient distributed approximation algorithms via probabilistic tree embeddings
title_short Efficient distributed approximation algorithms via probabilistic tree embeddings
title_full Efficient distributed approximation algorithms via probabilistic tree embeddings
title_fullStr Efficient distributed approximation algorithms via probabilistic tree embeddings
title_full_unstemmed Efficient distributed approximation algorithms via probabilistic tree embeddings
title_sort efficient distributed approximation algorithms via probabilistic tree embeddings
publishDate 2013
url https://hdl.handle.net/10356/98033
http://hdl.handle.net/10220/13238
_version_ 1681043431904772096