文章基本信息

标题：Submodular Optimization in the MapReduce Model
本地全文：下载
作者：Paul Liu ; Jan Vondrak
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2018
卷号：69
页码：1-10
DOI：10.4230/OASIcs.SOSA.2019.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Submodular optimization has received significant attention in both practice and theory, as a wide array of problems in machine learning, auction theory, and combinatorial optimization have submodular structure. In practice, these problems often involve large amounts of data, and must be solved in a distributed way. One popular framework for running such distributed algorithms is MapReduce. In this paper, we present two simple algorithms for cardinality constrained submodular optimization in the MapReduce model: the first is a (1/2-o(1))-approximation in 2 MapReduce rounds, and the second is a (1-1/e-epsilon)-approximation in (1+o(1))/epsilon MapReduce rounds.
关键词：mapreduce; submodular; optimization; approximation algorithms