- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies non-monotone k-submodular maximization under support constraints, and more generally full-domain orthant-submodular objectives satisfying r-wise monotonicity. Its first contribution is Random-root, a randomized greedy algorithm whose label distribution solves a local minimax problem based on support-charging losses. The algorithm obtains an explicit approximation factor for p-system constraints with value-oracle queries, where ρ is the maximum feasible support size. Its second contribution is a matroid-constrained continuous method using label-specific replacement losses and an adaptive comparison-weight potential. For non-monotone k-submodular objectives, it improves the recent matroid guarantee to , with , and obtains for and a guarantee above for all . The analysis further characterizes the exact local replacement-loss envelopes: for the envelope saturates once , whereas for the resulting coefficients plateau at three to five labels and then decrease. The paper supplies proofs, finite oracle implementations, and numerical checks of the theoretical coefficients, but no empirical evaluation of optimization performance on benchmark instances.
Critical strengths
-
The paper establishes genuinely new approximation guarantees in a well-studied setting. The improvement over the matroid guarantee of Chen et al. (2026b) is modest for but mathematically nontrivial, and the stronger coefficients for are more substantial. Random-root also extends the guarantee to -systems and to -wise monotone orthant-submodular objectives. These are concrete improvements over the results of Ye et al. (2025), Zhou et al. (2025), Huang et al. (2026), and Chen et al. (2026b), rather than merely an alternative analysis of the same approximation factor.
-
The label-specific comparison framework provides a substantive technical contribution beyond the final numerical constants. In particular, the distinction between support-budgeted and replacement losses (Proposition 4.1), the weighted potential transfer (Proposition 4.2), and the exact envelope classification across label counts (Section 5 and Appendix B) give a coherent explanation of when asymmetric label choices help. The paper also addresses finite implementation, estimation errors, and rounding rather than relying solely on an idealized continuous trajectory. This combination makes the work of independent theoretical interest.
Critical weaknesses
The practical benefits of the stronger approximation guarantees remain unclear. For , the continuous guarantee exceeds only when . The finite continuous algorithms have value-oracle complexity bounds with a dependence, whereas Random-root achieves queries without an accuracy parameter. Although these are worst-case upper bounds and both methods have comparable asymptotic dependence on for fixed , the additional sampling and continuous optimization may entail substantial computational overhead. Moreover, attaining some of the stronger label-dependent guarantees requires more elaborate local optimization, including a linear program for the exact coefficient when and . The manuscript provides no instance-level comparisons of objective quality, oracle usage, or running time against Random-root or existing methods; its figures illustrate theoretical coefficients rather than algorithmic performance. Consequently, while the theoretical improvements are valid and potentially significant, their practical benefits relative to simpler alternatives remain uncertain.
Questions for authors
-
Could the authors clarify the computational trade-off involved in obtaining a provable improvement over the existing guarantee under general matroid constraints? For , the guarantee exceeds only when . Although Theorem 6.2 provides a value-oracle complexity bound, it remains unclear how the required accuracy translates into practical oracle and arithmetic costs, including sampling, preprocessing, and rounding. A limited compute-matched comparison with Random-root and Chen et al. (2026b), using non-monotone instances of objective (3) under non-uniform matroid constraints and reporting achieved objective values, oracle calls, and running times, would help assess whether the refined continuous algorithm offers meaningful benefits at realistic computational budgets. Such a comparison would directly evaluate the proposed algorithmic contribution without requiring a broader application study.
-
Two very recent preprints, Aggarwal [1] and Wang & Wang [2], report stronger approximation guarantees for nonnegative non-monotone -submodular maximization under matroid constraints. Could the authors clarify how the contributions of the proposed label-specific replacement framework differ from these concurrent approaches, particularly regarding the exact envelope classification, broader -wise objective classes, and -system constraints? A brief comparison would help assess the independent significance and current positioning of the results.
[1] Geometry-Dependent Approximation for Non-Monotone k-Submodular Maximization.arXiv:2610.04049.
[2] An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint. arXiv:2610.20140.
4 comments
Concurrent work and independent contributions
Regarding the two recent preprints, Section 1.2 (pp. 2-3) now cites and compares both. Our original introduction foregrounded the coefficient improvements, while not sufficiently highlighting the contributions for the general case of ; the revised abstract and contribution section give greater prominence to the general results already present in Theorems 2.1-2.2.
General objective class and support constraints
We study full-domain -wise monotone orthant-submodular objectives, with -submodularity as the case. For , several labels of the same item may simultaneously have negative marginals. Random-root optimizes a local comparison incorporating both label choice and support-deletion costs. Its cumulative analysis yields the closed-form guarantee on general -systems in Theorem 2.1, using value queries.
On the common normalized nonnegative class under a matroid, Random-root improves the existing general -wise guarantee from to (Table 1, p. 2). The continuous algorithm further improves the baseline coefficient for every , with finite implementations attaining it up to any prescribed accuracy loss.
Exact replacement structure
Proposition 4.1 quantifies the local saving from retaining the displaced label. Section 5 and Appendix B determine the exact optimized replacement envelope through both attaining actions and matching upper bounds. For , throughout the parameter interval used by the algorithm, Thus, the first additional label supplies the full coefficient improvement available from this local replacement comparison. The pairwise case has a different structure: a three-to-five-label plateau followed by a decline. These results explain how label availability changes the optimal local action and its resulting guarantee, beyond reporting a final approximation number.
Relation to the concurrent approaches
Aggarwal (arXiv:2610.04049v2) derives coefficients depending on the geometry of the feasible support region, measured by the largest selection probability feasible uniformly for all elements. Wang et al. (arXiv:2610.20140v2) combine a top-two label rule with a nested-chain potential and maximum-weight matroid bases. Our route instead optimizes the local comparison over the general -wise domain and classifies its exact replacement envelopes, using cumulative support losses and a matroid potential to obtain the global guarantees.
On the common nonnegative, non-monotone -submodular single-matroid problem, the concurrent works report stronger coefficients, including Wang et al.'s 0.48 guarantee; the revised related work explicitly acknowledges this. Our independent contributions are the algorithms and improved guarantees for general constrained -wise objectives, the -system result, and the exact label-replacement structure. Theorem 6.1 and Appendix C.5 connect these structural results to finite algorithms with explicit query bounds.
Follow-up on our responses
Thank you again for your detailed suggestions. As the discussion period draws to a close, we would appreciate it if you could take a look at our two responses and the revised manuscript.
They address the computational cost of the stronger guarantee, the requested comparison with Root and Chen in Appendix F.3, and the relationship to the two recent papers.
We would be grateful to hear whether these responses address your main concerns, or whether there is a particular point we could clarify further.
Thank you for your time.
Thank you for the detailed responses and revisions. The additional complexity analysis and compute-matched experiments substantially address my concerns about computational practicality, although the two-label results do not show a clear advantage over Chen et al. (2026b). The comparison with concurrent work also clarifies the paper's independent theoretical contributions, particularly the general (r)-wise framework and exact replacement-loss envelopes.
I will revise my recommendation to Weak Accept.
Certified costs and compute-matched comparisons
Thank you for the detailed assessment and the concrete suggestion for a compute-matched comparison. We have made the precision-dependent costs more explicit and added the requested two-label experiment alongside the general r-wise experiments. Selected substantive revisions are highlighted in blue; all locations below refer to the revised manuscript.
Cost of a provably stronger guarantee
The original presentation emphasized the O(nkρ) query order at fixed accuracy. Section 6 now explicitly connects the desired guarantee to the additional precision cost. Your two-label threshold is correct: under the theorem's sampling prescription, a strict improvement requires τ<α2−(2−1)≈0.00758. Theorem 6.1 (formerly Theorem 6.2) and the discussion on p. 9 show that, for fixed r, the sparse continuous bound adds a precision factor τ−3log(1/τ) relative to Root's O(nkρ) bound. Appendix D.6 gives complete sufficient query budgets for a target coefficient γ, using tolerances αr−γ and ar,k−γ for the sparse and refined full-row routes, respectively.
The accounting includes preprocessing, sampled contexts, and output evaluation. Beyond oracle calls, Appendix D.5 accounts for the O(n) construction of an explicit sampled context, while Appendix C.4 describes support exchanges and finite-bit sampling. The local LP is specific to the fixed-label refinement for r=2,k≥4; the experiments use the sparse continuous baseline and do not invoke that LP.
The requested two-label, non-uniform-matroid experiment
Appendix F.3 (p. 46) uses a modular-coverage special case of the original objective (3), retaining nonnegativity, non-monotonicity, and k=r=2. Its 16 elements form eight pairs with at most one selected per pair, a non-uniform partition matroid of rank eight. We test six instances under each of two audience arrangements, with three independent randomized trials per instance.
In each trial, one complete continuous run determines the time allowance T. Random-root and Chen each start from empty and spend the same allowance on their own restarts, retaining their best feasible return. All methods use the same value oracle. Continuous optimization is charged for initialization, preprocessing, sampling, updates, compression, rounding, and output evaluation.
In the high-competition group, the median allowance is 0.756 seconds. Time-matched Root, continuous optimization, and Chen attain 95.86%, 97.59%, and 100% of OPT, with median query counts of approximately 428,000, 100,000, and 457,000, respectively. Chen is strongest in this group; under ordinary overlap all three methods reach OPT. Table 3 also reports equal-query results. The cost breakdown below it shows that continuous updates, including sampling, compression, and rounding, take a median 0.751 seconds; Greedy initialization and scale preprocessing take 0.45 ms and 0.26 ms.
Additional value in the general r-wise setting
Section 7 examines strict r=3,6 instances. In Figure 1's high-overlap r=6 group (p. 10), continuous optimization and time-matched Root restarts reach 90.34% and 84.48% of OPT. Continuous exceeds Root's full-budget best in 17 of 18 paired trials; among those 17, the median fraction of the budget needed to first exceed it is 26%. All six instances improve on average, and the equal-query comparison in Appendix F.2 also favors continuous optimization.
The empirical runs use fixed τ=0.1 and N=2 samples per marginal estimate to measure performance at limited computation. The stronger worst-case guarantee uses the target-dependent sampling prescription above. These complementary analyses quantify both the sufficient cost of certifying an improvement and the better feasible solutions obtained in practice under matched budgets.