Fast distributed algorithms for Lp-type problems of low dimension

Kristian Hinnenthal, Christian Scheideler, Martijn Struijs

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

9 Downloads (Pure)

Samenvatting

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.

Originele taal-2Engels
Titel33rd International Symposium on Distributed Computing, DISC 2019
RedacteurenJukka Suomela
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's16
ISBN van elektronische versie9783959771269
DOI's
StatusGepubliceerd - 1 okt 2019
Evenement33rd International Symposium on Distributed Computing, DISC 2019 - Budapest, Hongarije
Duur: 14 okt 201918 okt 2019

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
Volume146
ISSN van geprinte versie1868-8969

Congres

Congres33rd International Symposium on Distributed Computing, DISC 2019
LandHongarije
StadBudapest
Periode14/10/1918/10/19

Vingerafdruk Duik in de onderzoeksthema's van 'Fast distributed algorithms for Lp-type problems of low dimension'. Samen vormen ze een unieke vingerafdruk.

Citeer dit