@inproceedings{942927b0428a4c46887e4938dc606334,
title = "Distributed approximate k-core decomposition and min-max edge orientation: Breaking the diameter barrier",
abstract = "We design distributed algorithms to compute approximate solutions for several related graph optimization problems. All our algorithms have round complexity being logarithmic in the number of nodes of the underlying graph and in particular independent of the graph diameter. By using a primal-dual approach, we develop a 2(1 + ε)-approximation algorithm for computing the coreness values of the nodes in the underlying graph, as well as a 2(1 + ε)-approximation algorithm for the min-max edge orientation problem, where the goal is to orient the edges so as to minimize the maximum weighted in-degree. We provide lower bounds showing that the aforementioned algorithms are tight both in terms of the approximation guarantee and the round complexity. Finally, motivated by the fact that the densest subset problem has an inherent dependency on the diameter of the graph, we study a weaker version that does not suffer from the same limitation.",
keywords = "Coreness, Distributed algorithms, Round complexity",
author = "\{Hubert Chan\}, \{T. H.\} and Mauro Sozio and Bintao Sun",
note = "Publisher Copyright: {\textcopyright} 2019 IEEE; 33rd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019 ; Conference date: 20-05-2019 Through 24-05-2019",
year = "2019",
month = may,
day = "1",
doi = "10.1109/IPDPS.2019.00044",
language = "English",
series = "Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "345--354",
booktitle = "Proceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium, IPDPS 2019",
}