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

Kristian Hinnenthal, Christian Scheideler, Martijn Struijs

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

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.

Originele taal-2Engels
TitelSPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Pagina's393-394
Aantal pagina's2
ISBN van elektronische versie978-1-4503-6184-2
DOI's
StatusGepubliceerd - 17 jun 2019
Evenement31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 - Phoenix, Verenigde Staten van Amerika
Duur: 22 jun 201924 jun 2019

Congres

Congres31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019
LandVerenigde Staten van Amerika
StadPhoenix
Periode22/06/1924/06/19

Vingerafdruk

Duik in de onderzoeksthema's van 'Fast distributed algorithms for LP-Type problems of bounded dimension (brief announcement)'. Samen vormen ze een unieke vingerafdruk.

Citeer dit