文章基本信息

标题：Fast Distributed Algorithms for LP-Type Problems of Low Dimension
本地全文：下载
作者：Kristian Hinnenthal ; Christian Scheideler ; Martijn Struijs 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：146
页码：1-16
DOI：10.4230/LIPIcs.DISC.2019.23
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：LP-type problems; linear optimization; distributed algorithms; gossip algorithms