Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation

We thank the reviewer for the thoughtful feedback. Regarding the suggestions related to paper presentation and organization, we have provided detailed responses to each point in our reply to Reviewer KJuz. For other questions, we address each point below.

The authors state that they only provide the results for er in the main body, but the results for twitch-gamers are also given there.

Thank you for pointing this out. We will correct our statement in the next version.

The selection criterion of baseline methods is unclear. 

Thank you for the suggestion. In our current experiments, we focused on parallel algorithms designed specifically for size-constrained problems. While algorithms like ParKnapsack, ParSKP, and ParSSP can handle more complex constraints, such as knapsack constraints, they currently suffer from high query complexity, which limits their practicality. For completeness, we plan to include experimental results for these algorithms in our next version.

... it seems unfair to employ a random subset for the algorithms that require to solve the unconstrained problem.

We appreciate the reviewer’s observation regarding the use of a random subset for baseline methods that require solving the unconstrained problem. We would like to clarify the rationale behind our experimental design:

• The $1/2$-approximation constant-adaptive algorithm proposed by [1] is used for ANM, AST, and ATG. However, this algorithm relies on querying the multilinear extension $F$ of the objective function, whose estimation requires an impractically large number of queries to the value oracle $f$. This makes the algorithm prohibitively expensive to run in experiments, despite its theoretical guarantees.
• Based on our experimental evaluation, the solutions returned by unconstrained algorithms (e.g., [1]) do not dominate other solutions. Thus, their inclusion would not meaningfully improve objective values in practice.
• In summary, while implementing [1] would align with theoretical comparisons, it would incur significant query complexity without commensurate gains in solution quality. Our goal was to focus on practical and scalable baselines, which better reflect real-world constraints.

[1] Chen, L., Feldman, M., & Karbasi, A. (2019). Unconstrained submodular maximization with constant adaptive complexity. In Charikar, M., & Cohen, E. (Eds.), Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pp. 102–113. ACM.

The problem of maximizing non-monotone submodular functions is not motivated accordingly. Indeed, the application examples listed by the authors are mostly with monotone submodular functions (e.g., influence maximization).

We appreciate the reviewer’s feedback. For the same application, different submodular functions can be defined as either monotone or non-monotone. For example, influence maximization can have non-monotone variants when considering competition or oversaturation effects.

We also acknowledge that some of our cited papers focus on monotone functions. To clarify this distinction, we will differentiate between monotone and non-monotone papers and add the following paper as a non-monotone variant for the revenue maximization application.

• Amanatidis, Georgios, et al. "Fast adaptive non-monotone submodular maximization subject to a knapsack constraint." Advances in neural information processing systems 33 (2020).

... but the approximation ratio itself is nothing new, so mentioning it as one of the proposals would be weird for the readers ...

We appreciate this insightful observation. While the 1/4-approximation ratio itself is not novel, our algorithm achieve this ratio with high probability ($\ge 1-1/n$). In Cui et al. (2023), ParSSP achieves $1/4$ approximation ratio in expectation. We will revise our abstract as follows which leads with our primary 1/e-approximation result and present the 1/4-result as a byproduct.

"... In this work, we focus on size constraints and present the first combinatorial algorithm matching this bound - a randomized parallel approach achieving $1/e − \varepsilon$ approximation ratio. This result bridges the gap between continuous and combinatorial approaches for this problem. As a byproduct, we also develop a simpler $(1/4 − \varepsilon)$-approximation algorithm with high probability $( \ge 1 − 1/n)$..."

In Section 3.1, the authors state that intuitively adding an element from $O$... just meaning that the first step can be eliminated.

We sincerely appreciate this insightful observation. We agree that the explanation here might be misleading. We will revise the text to remove ambiguous descriptions as follows.

"This complex architecture naturally raises a fundamental question: Can we develop an alternative analysis framework that eliminates the need to explicitly guess the position of $o_{\max}$?"

We thank the reviewer for the constructive comments. Regarding the suggestions related to paper presentation and organization, we have provided detailed responses to each point in our reply to Reviewer KJuz.

The results provide marginal improvement compared to the state of the art.

We sincerely appreciate the reviewer’s feedback. While the improvement in approximation ratio may appear incremental at first glance, we would like to clarify the significance of our contribution.

Our work represents the first advancement in five years since the breakthrough $1/e$-approximation achieved by a parallel continuous algorithm (Ene & Nguyen, 2020). Specifically, we improve the approximation ratio for parallel combinatorial algorithms from $1/4$ to $1/e$, bridging a key gap between combinatorial and continuous approaches. Given that the current best-known approximation ratio for non-monotone submodular maximization is 0.401 [1], an improvement exceeding 0.11 is, in fact, a meaningful step forward in this challenging problem space.

[1] Buchbinder, N. and Feldman, M. Constrained submodular maximization via new bounds for dr-submodular functions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC, 2024.

We thank the reviewers for their constructive suggestions. We will revise the manuscript to improve clarity and presentation. In Section 1.1, we clarify the technical contributions, focusing on how the simplified InterpolatedGreedy enables parallelization and enhancing the explanation of our parallel algorithm (PIG). In Section 2, we refine definitions of adaptivity, parallel algorithms, and the thresholding technique. We restructure Section 3, remove Section 4 for conciseness, and improve Section 5 with an overview, pseudocode, and key subroutine introductions.

Below, we detail these changes.

1. Section 1.1. Contributions.

   • Our first contribution is a technical contribution that simplifies both InterpolatedGreedy and InterlaceGreedy. Importantly, by eliminating the low-success-probability requirement, the simplified InterpolatedGreedy serves as an efficient framework for parallel algorithm design. We will clarify this in the revised manuscript as follows.

   "... Most importantly, these simplified variants establish the theoretical foundation for parallel algorithms. By removing branching dependencies and probabilistic guesswork, our framework enables the first efficient parallelization of these interlaced greedy approaches while preserving their approximation guarantees."

   • Our second contribution is the proposed parallel algorithms, where we explain how integrating the interlaced greedy approach with threshold sampling achieves both theoretical guarantees and practical efficiency. The revised version is below.

   "... The core innovation of PIG lies in its novel threshold sampling procedure, which simultaneously preserves the crucial alternating selection property of interlaced greedy methods while enabling efficient parallel implementation.

   Like prior parallel algorithms, PIG maintains descending thresholds for each solution, adding elements whose average marginal gain exceeds the current threshold. However, PIG introduces two critical modifications to maintain the interlaced greedy structure: 1) strict synchronization of batch sizes across all $\ell$ parallel solutions, and 2) coordinated element selection to maintain sufficient marginal gain for each solution.

   This design achieves three fundamental properties. First, it preserves the essential alternating selection property of the interlaced greedy methods. Second, through threshold sampling, it geometrically reduces the size of candidate sets - crucial for achieving sublinear adaptivity. Third, its efficient batch selection ensures each added batch provides sufficient marginal contribution to the solution. Together, these properties allow PIG to match the approximation guarantees of the vanilla interlaced greedy method while achieving parallel efficiency..."

2. Section 2. Preliminary

   • We will include formal definitions of adaptivity and parallel algorithms in the revised manuscript. Additionally, we will clarify the concept of sublinear adaptive algorithm.
   • We will provide a concise introduction to the thresholding technique, explaining its role in the parallel algorithms.

3. Section 3. The Blending Technique for Greedy

   • We will retitle this section as "A Parallel-Friendly Greedy Variant via Blending Technique" to better reflect its focus on developing an efficient parallelizable algorithm.
   • We will focus on the simplified InterpolatedGreedy (achieving a $1/e$-approximation) and leave the simplified InterlaceGreedy (achieving a $1/4$-approximation) in appendix.
   • The structure of the section will be as follows:
     • Section 3.1: An Overview of Prior Work and Its Limitation.
       • Summarizes how InterpolatedGreedy works and identifies key bottlenecks for parallelization.
     • Section 3.2: Motivation for Simplification.
       • Explains the rationale behind our approach and its advantages.
     • Section 3.3: Technical Overview of Blended Marginal Gains Strategy for InterpolatedGreedy.
       • Provides a high-level explanation of how the blended marginal gains strategy enhances InterpolatedGreedy's efficiency.

4. Section 4. Preliminary Warm-Up of Parallel Approaches: Nearly-Linear Time Algorithms (Removal)

   • To streamline the presentation and avoid redundancy, we will remove this section. This adjustment allows us to dedicate more space to Sections 3 and 5, where we will elaborate on the high-level ideas and technical details of the proposed algorithms.

5. Section 5. Sublinear Adaptive Algorithms

   • Section 5.1: Subroutines for PIG.
     • This subsection will include the pseudocodes for key subroutines (Distribute, Update, Prefix-Selection) and provide a high-level description of their functionality.
   • Section 5.2: Algorithm Overview
     • Here, we will introduce the core intuition behind the algorithm, emphasizing its novel components and how they collectively achieve sublinear adaptivity.

Their experiments seem reasonable, but the graph on solution value is missing the data for the ATG algorithm, which appears to have better adaptivity and query complexity.

Thank you for pointing this out. Since the objective value is normalized by ATG, the ATG data would appear as a horizontal line with value 1 in the graph. To improve clarity, we will add this line to the graph.

Comparing with PARSSP would also be interesting, as it achieves better approximation factors than other logarithmic adaptivity algorithms.

Thank you for the suggestion, we will add the comparison to PARSSP in the next version.