Paper Info
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.
Year
DOI
Venue
2019
10.1145/3323165.3323174
SPAA'19: PROCEEDINGS OF THE 31ST ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURESS, 2019
Keywords
Field
DocType
LP-type problems,abstract optimization problems,abstract linear programs,distributed algorithms,gossip model
Convergence (routing),Integer,Set cover problem,Computer science,Parallel computing,Gossip,Theoretical computer science,Distributed algorithm,Polytope,Linear programming,Bounded function
Conference
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Kristian Hinnenthal142.17
Christian Scheideler21729152.71
Martijn Struijs311.71