Submodular Optimization Developments

The field of submodular optimization is moving towards the development of more efficient and scalable algorithms for various submodular problems. Researchers are focusing on improving the approximation guarantees and reducing the query complexity of existing algorithms, making them more practical for large-scale real-world applications. Notably, the use of stochastic greedy algorithms and LP-relaxations is becoming increasingly popular. These advancements have the potential to impact various areas, including artificial intelligence, combinatorial optimization, and resource allocation. Noteworthy papers include: The paper on the Fast Stochastic Greedy Algorithm for k-Submodular Cover Problem, which achieves strong bicriteria approximation while substantially lowering query complexity. The paper on the Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint, which proposes two approximation algorithms with improved query complexity and solution quality.

Sources

An Approximation Algorithm for Monotone Submodular Cost Allocation

Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem

Finding Probably Approximate Optimal Solutions by Training to Estimate the Optimal Values of Subproblems

Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint

Built with on top of