Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models

DOI10.1613/jair.1.15484zbMATH Open1546.68038MaRDI QIDQ6599123

Tonmoy Dey, Yi-Xin Chen, Alan Kuhnle

Publication date: 5 September 2024

Published in: The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationmachine learningoptimization algorithmdistributed constraint optimization

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Submodular optimization problems and greedy strategies: a survey
• Randomized Composable Core-sets for Distributed Submodular Maximization
• A Review for Submodular Optimization on Machine Scheduling Problems
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Non-monotone submodular maximization under matroid and knapsack constraints
• The adaptive complexity of maximizing a submodular function
• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Submodular Function Maximization in Parallel via the Multilinear Relaxation
• Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization
• Submodular Maximization with Cardinality Constraints
• Fast algorithms for maximizing submodular functions
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Submodular optimization in the MapReduce model

This page was built for publication: Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models