2026-07-22T06:32:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10044 2024-03-06T10:30:34Z ddc:004 open_access

Submodular Optimization in the MapReduce Model Liu, Paul Vondrak, Jan mapreduce submodular optimization approximation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paul Liu and Jan Vondrak 2019 Is Part Of OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2019.18 urn:nbn:de:0030-drops-100447 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.18 eng https://creativecommons.org/licenses/by/3.0/legalcode