arXiv
Open Access
2018
Submodular Optimization in the MapReduce Model
Paul Liu
Jan Vondrak
Abstrak
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-ε)$-approximation in $\frac{1+o(1)}ε$ MapReduce rounds.
Topik & Kata Kunci
Penulis (2)
P
Paul Liu
J
Jan Vondrak
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2018
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓