Fast distributed algorithms for LP-Type problems of bounded dimension (brief announcement)

Kristian Hinnenthal; Christian Scheideler; Martijn Struijs

doi:10.1145/3323165.3323174

Fast distributed algorithms for LP-Type problems of bounded dimension (brief announcement)

Kristian Hinnenthal, Christian Scheideler, Martijn Struijs

Algorithms, Geometry and Applications

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

Abstract

In this brief announcement we summarize our results concerning 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 language	English
Title of host publication	SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures
Place of Publication	New York
Publisher	Association for Computing Machinery, Inc
Pages	393-394
Number of pages	2
ISBN (Electronic)	978-1-4503-6184-2
DOIs	https://doi.org/10.1145/3323165.3323174
Publication status	Published - 17 Jun 2019
Event	31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 - Phoenix, United States Duration: 22 Jun 2019 → 24 Jun 2019

Conference

Conference	31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019
Country/Territory	United States
City	Phoenix
Period	22/06/19 → 24/06/19

Keywords

Abstract linear programs
Abstract optimization problems
Distributed algorithms
Gossip model
LP-type problems
abstract linear programs
abstract optimization problems
distributed algorithms
gossip model

Access to Document

10.1145/3323165.3323174

Cite this

@inproceedings{6d9184542e3f472ea793c752780f2ac8,

title = "Fast distributed algorithms for LP-Type problems of bounded dimension (brief announcement)",

abstract = "In this brief announcement we summarize our results concerning 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 = "Abstract linear programs, Abstract optimization problems, Distributed algorithms, Gossip model, LP-type problems, abstract linear programs, abstract optimization problems, distributed algorithms, gossip model",

author = "Kristian Hinnenthal and Christian Scheideler and Martijn Struijs",

year = "2019",

month = jun,

day = "17",

doi = "10.1145/3323165.3323174",

language = "English",

pages = "393--394",

booktitle = "SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

note = "31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 ; Conference date: 22-06-2019 Through 24-06-2019",

}

Hinnenthal, K, Scheideler, C & Struijs, M 2019, Fast distributed algorithms for LP-Type problems of bounded dimension (brief announcement). in SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, Inc, New York, pp. 393-394, 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, United States, 22/06/19. https://doi.org/10.1145/3323165.3323174

Fast distributed algorithms for LP-Type problems of bounded dimension (brief announcement). / Hinnenthal, Kristian; Scheideler, Christian; Struijs, Martijn.

SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures. New York : Association for Computing Machinery, Inc, 2019. p. 393-394.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Fast distributed algorithms for LP-Type problems of bounded dimension (brief announcement)

AU - Hinnenthal, Kristian

AU - Scheideler, Christian

AU - Struijs, Martijn

PY - 2019/6/17

Y1 - 2019/6/17

N2 - In this brief announcement we summarize our results concerning 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 brief announcement we summarize our results concerning 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 - Abstract linear programs

KW - Abstract optimization problems

KW - Distributed algorithms

KW - Gossip model

KW - LP-type problems

KW - abstract linear programs

KW - abstract optimization problems

KW - distributed algorithms

KW - gossip model

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

U2 - 10.1145/3323165.3323174

DO - 10.1145/3323165.3323174

M3 - Conference contribution

AN - SCOPUS:85068702569

SP - 393

EP - 394

BT - SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery, Inc

CY - New York

T2 - 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019

Y2 - 22 June 2019 through 24 June 2019

ER -

Fast distributed algorithms for LP-Type problems of bounded dimension (brief announcement)

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this