Efficient distributed approximation algorithms via probabilistic tree embeddings

• 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
• Institution: Nanyang Technological University

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