Fast Parallel Algorithms for Submodular $p$-Superseparable Maximization

Abstract

Maximizing a non-negative, monontone, submodular function $f$ over $n$ elements under a cardinality constraint $k$ (SMCC) is a well-studied NP-hard problem. It has important applications in, e.g., machine learning and influence maximization. Though the theoretical problem admits polynomial-time approximation algorithms, solving it in practice often involves frequently querying submodular functions that are expensive to compute. This has motivated significant research into designing parallel approximation algorithms in the adaptive complexity model; adaptive complexity (adaptivity) measures the number of sequential rounds of $\text{poly}(n)$ function queries an algorithm requires. The state-of-the-art algorithms can achieve $(1-\frac{1}{e}-\epsilon )$-approximate solutions with $O(\frac{1}{{\epsilon }^2}\log n)$ adaptivity, which approaches the known adaptivity lower-bounds. However, the $O(\frac{1}{{\epsilon }^2}\log n)$ adaptivity only applies to maximizing worst-case functions that are unlikely to appear in practice. Thus, in this paper, we consider the special class of $p$-superseparable submodular functions, which places a reasonable constraint on $f$, based on the parameter $p$, and is more amenable to maximization, while also having real-world applicability. Our main contribution is the algorithm LS+GS, a finer-grained version of the existing LS+PGB algorithm, designed for instances of SMCC when $f$ is $p$-superseparable; it achieves an expected $(1-\frac{1}{e}-\epsilon )$-approximate solution with $O(\frac{1}{{\epsilon }^2}\log (pk))$ adaptivity independent of $n$. Additionally, unrelated to $p$-superseparability, our LS+GS algorithm uses only $O(\frac{n}{\epsilon }+\frac{\log n}{{\epsilon }^2})$ oracle queries, which has an improved dependence on ${\epsilon }^{-1}$ over the state-of-the-art LS+PGB; this is achieved through the design of a novel thresholding subroutine.

arXiv comment36 pages. To be published in Approximation and Online Algorithms (Proceedings of the 21st International Workshop, WAOA 2023)

References in corpus (7)

• Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
• Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
• Scalable Greedy Feature Selection via Weak Submodularity
• The FAST Algorithm for Submodular Maximization
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel
• Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time