Bicriteria Distributed Submodular Maximization in a Few Rounds
| Autor: | Morteza Zadimoghaddam, Vahab Mirrokni, Alessandro Epasto |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Submodular maximization
Computation Value (computer science) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Submodular set function Combinatorics Set (abstract data type) Cardinality 010201 computation theory & mathematics Distributed algorithm 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Constant (mathematics) Mathematics |
| Zdroj: | SPAA |
| DOI: | 10.1145/3087556.3087574 |
| Popis: | We study the problem of efficiently optimizing submodular functions under cardinality constraints in distributed setting. Recently, several distributed algorithms for this problem have been introduced which either achieve a sub-optimal solution or they run in super-constant number of rounds of computation. Unlike previous work, we aim to design distributed algorithms in multiple rounds with almost optimal approximation guarantees at the cost of outputting a larger number of elements. Toward this goal, we present a distributed algorithm that, for any e > 0 and any constant r, outputs a set S of O(rk/e1/r) items in r rounds, and achieves a (1-e)-approximation of the value of the optimum set with k items. This is the first distributed algorithm that achieves an approximation factor of (1-e) running in less than log 1/e number of rounds. We also prove a hardness result showing that the output of any 1-e approximation distributed algorithm limited to one distributed round should have at least Ω(k/e) items. In light of this hardness result, our distributed algorithm in one round, r = 1, is asymptotically tight in terms of the output size. We support the theoretical guarantees with an extensive empirical study of our algorithm showing that achieving almost optimum solutions is indeed possible in a few rounds for large-scale real datasets. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|