Fast distributed algorithms for Lp-type problems of low dimension

Kristian Hinnenthal, Christian Scheideler, Martijn Struijs

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

Abstract

In this paper we present various distributed algorithms for LP-type problems in the well-known gossip model. LP-type problems include many important classes of problems such as (integer) linear programming, geometric problems like smallest enclosing ball and polytope distance, and set problems like hitting set and set cover. In the gossip model, a node can only push information to or pull information from nodes chosen uniformly at random. Protocols for the gossip model are usually very practical due to their fast convergence, their simplicity, and their stability under stress and disruptions. Our algorithms are very efficient (logarithmic rounds or better with just polylogarithmic communication work per node per round) whenever the combinatorial dimension of the given LP-type problem is constant, even if the size of the given LP-type problem is polynomially large in the number of nodes.

Original languageEnglish
Title of host publication33rd International Symposium on Distributed Computing, DISC 2019
EditorsJukka Suomela
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages16
ISBN (Electronic)9783959771269
DOIs
Publication statusPublished - 1 Oct 2019
Event33rd International Symposium on Distributed Computing, DISC 2019 - Budapest, Hungary
Duration: 14 Oct 201918 Oct 2019

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume146
ISSN (Print)1868-8969

Conference

Conference33rd International Symposium on Distributed Computing, DISC 2019
CountryHungary
CityBudapest
Period14/10/1918/10/19

Fingerprint

Parallel algorithms
Linear programming
Network protocols
Communication

Keywords

  • Distributed algorithms
  • Gossip algorithms
  • Linear optimization
  • LP-type problems

Cite this

Hinnenthal, K., Scheideler, C., & Struijs, M. (2019). Fast distributed algorithms for Lp-type problems of low dimension. In J. Suomela (Ed.), 33rd International Symposium on Distributed Computing, DISC 2019 [23] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 146). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2019.23
Hinnenthal, Kristian ; Scheideler, Christian ; Struijs, Martijn. / Fast distributed algorithms for Lp-type problems of low dimension. 33rd International Symposium on Distributed Computing, DISC 2019. editor / Jukka Suomela. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. (Leibniz International Proceedings in Informatics (LIPIcs)).
@inproceedings{5c0fb5c14cb746e991a6733f1065eff6,
title = "Fast distributed algorithms for Lp-type problems of low dimension",
abstract = "In this paper we present various distributed algorithms for LP-type problems in the well-known gossip model. LP-type problems include many important classes of problems such as (integer) linear programming, geometric problems like smallest enclosing ball and polytope distance, and set problems like hitting set and set cover. In the gossip model, a node can only push information to or pull information from nodes chosen uniformly at random. Protocols for the gossip model are usually very practical due to their fast convergence, their simplicity, and their stability under stress and disruptions. Our algorithms are very efficient (logarithmic rounds or better with just polylogarithmic communication work per node per round) whenever the combinatorial dimension of the given LP-type problem is constant, even if the size of the given LP-type problem is polynomially large in the number of nodes.",
keywords = "Distributed algorithms, Gossip algorithms, Linear optimization, LP-type problems",
author = "Kristian Hinnenthal and Christian Scheideler and Martijn Struijs",
year = "2019",
month = "10",
day = "1",
doi = "10.4230/LIPIcs.DISC.2019.23",
language = "English",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
editor = "Jukka Suomela",
booktitle = "33rd International Symposium on Distributed Computing, DISC 2019",

}

Hinnenthal, K, Scheideler, C & Struijs, M 2019, Fast distributed algorithms for Lp-type problems of low dimension. in J Suomela (ed.), 33rd International Symposium on Distributed Computing, DISC 2019., 23, Leibniz International Proceedings in Informatics (LIPIcs), vol. 146, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 33rd International Symposium on Distributed Computing, DISC 2019, Budapest, Hungary, 14/10/19. https://doi.org/10.4230/LIPIcs.DISC.2019.23

Fast distributed algorithms for Lp-type problems of low dimension. / Hinnenthal, Kristian; Scheideler, Christian; Struijs, Martijn.

33rd International Symposium on Distributed Computing, DISC 2019. ed. / Jukka Suomela. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. 23 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 146).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Fast distributed algorithms for Lp-type problems of low dimension

AU - Hinnenthal, Kristian

AU - Scheideler, Christian

AU - Struijs, Martijn

PY - 2019/10/1

Y1 - 2019/10/1

N2 - In this paper we present various distributed algorithms for LP-type problems in the well-known gossip model. LP-type problems include many important classes of problems such as (integer) linear programming, geometric problems like smallest enclosing ball and polytope distance, and set problems like hitting set and set cover. In the gossip model, a node can only push information to or pull information from nodes chosen uniformly at random. Protocols for the gossip model are usually very practical due to their fast convergence, their simplicity, and their stability under stress and disruptions. Our algorithms are very efficient (logarithmic rounds or better with just polylogarithmic communication work per node per round) whenever the combinatorial dimension of the given LP-type problem is constant, even if the size of the given LP-type problem is polynomially large in the number of nodes.

AB - In this paper we present various distributed algorithms for LP-type problems in the well-known gossip model. LP-type problems include many important classes of problems such as (integer) linear programming, geometric problems like smallest enclosing ball and polytope distance, and set problems like hitting set and set cover. In the gossip model, a node can only push information to or pull information from nodes chosen uniformly at random. Protocols for the gossip model are usually very practical due to their fast convergence, their simplicity, and their stability under stress and disruptions. Our algorithms are very efficient (logarithmic rounds or better with just polylogarithmic communication work per node per round) whenever the combinatorial dimension of the given LP-type problem is constant, even if the size of the given LP-type problem is polynomially large in the number of nodes.

KW - Distributed algorithms

KW - Gossip algorithms

KW - Linear optimization

KW - LP-type problems

UR - http://www.scopus.com/inward/record.url?scp=85074613377&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.DISC.2019.23

DO - 10.4230/LIPIcs.DISC.2019.23

M3 - Conference contribution

AN - SCOPUS:85074613377

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 33rd International Symposium on Distributed Computing, DISC 2019

A2 - Suomela, Jukka

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

ER -

Hinnenthal K, Scheideler C, Struijs M. Fast distributed algorithms for Lp-type problems of low dimension. In Suomela J, editor, 33rd International Symposium on Distributed Computing, DISC 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2019. 23. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.DISC.2019.23