License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.35
URN: urn:nbn:de:0030-drops-98245
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9824/
Kawarabayashi, Ken-ichi ;
Schwartzman, Gregory
Adapting Local Sequential Algorithms to the Distributed Setting
Abstract
It is a well known fact that sequential algorithms which exhibit a strong "local" nature can be adapted to the distributed setting given a legal graph coloring. The running time of the distributed algorithm will then be at least the number of colors. Surprisingly, this well known idea was never formally stated as a unified framework. In this paper we aim to define a robust family of local sequential algorithms which can be easily adapted to the distributed setting. We then develop new tools to further enhance these algorithms, achieving state of the art results for fundamental problems.
We define a simple class of greedy-like algorithms which we call orderless-local algorithms. We show that given a legal c-coloring of the graph, every algorithm in this family can be converted into a distributed algorithm running in O(c) communication rounds in the CONGEST model. We show that this family is indeed robust as both the method of conditional expectations and the unconstrained submodular maximization algorithm of Buchbinder et al. [Niv Buchbinder et al., 2015] can be expressed as orderless-local algorithms for local utility functions - Utility functions which have a strong local nature to them.
We use the above algorithms as a base for new distributed approximation algorithms for the weighted variants of some fundamental problems: Max k-Cut, Max-DiCut, Max 2-SAT and correlation clustering. We develop algorithms which have the same approximation guarantees as their sequential counterparts, up to a constant additive epsilon factor, while achieving an O(log^* n) running time for deterministic algorithms and O(epsilon^{-1}) running time for randomized ones. This improves exponentially upon the currently best known algorithms.
BibTeX - Entry
@InProceedings{kawarabayashi_et_al:LIPIcs:2018:9824,
author = {Ken-ichi Kawarabayashi and Gregory Schwartzman},
title = {{Adapting Local Sequential Algorithms to the Distributed Setting}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {35:1--35:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-092-7},
ISSN = {1868-8969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9824},
URN = {urn:nbn:de:0030-drops-98245},
doi = {10.4230/LIPIcs.DISC.2018.35},
annote = {Keywords: Distributed, Approximation Algorithms, Derandomization, Max-Cut}
}
|
Keywords: |
|
Distributed, Approximation Algorithms, Derandomization, Max-Cut |
|
Collection: |
|
32nd International Symposium on Distributed Computing (DISC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.10.2018 |
