- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies cost-aware submodular maximization under a cardinality constraint when elements can be inserted and deleted. BatchReg maintains a feasible solution with a regularized approximation guarantee and polylogarithmic expected amortized value-oracle query complexity. The guarantee assumes that the update sequence is independent of the algorithm's random choices. The algorithm groups candidates by distorted marginal gain and cost, selects filtered random batches, and reconstructs affected parts of a layered data structure. Experiments on maximum coverage using Slashdot compare solution values and oracle queries with two streaming algorithms that restart after deletions.
Critical strengths
-
The paper addresses a gap between regularized streaming algorithms and fully dynamic submodular maximization. Supporting both insertions and deletions while maintaining a regularized approximation guarantee with polylogarithmic expected amortized query complexity is a useful theoretical result.
-
The algorithm's components address concrete difficulties in dynamic maintenance. Joint bucketing accounts for differences in cost among elements with similar distorted gains. Filtered batch selection checks that accepted elements still meet the gain threshold, while suffix reconstruction confines rebuilding to the affected part of the layered structure.
Critical weaknesses
-
The paper does not report batch-size statistics or the estimator's share of total queries. These measurements would clarify the practical cost of batch selection.
-
Figure 1 omits solution sizes and best-singleton output frequency. It is therefore unclear whether the tested cardinality limits substantially affect the solutions.
-
Both baselines restart after every deletion. This provides a useful reference, but a maintenance heuristic and wall-clock measurements would give a fuller picture of practical efficiency.
-
The experiments use one graph, a fixed active window, and random deletions, without reporting variation across independent runs. The empirical evidence for performance across different settings remains limited.
Questions for authors
-
In Figure 1, how many elements does BatchReg typically select? Does it often return the best singleton? I could not tell whether the cardinality limit affects the solutions in these experiments.
-
Both baselines restart after every deletion. How much of the reported advantage remains against a baseline that rebuilds less often? A wall-clock comparison would help put the query reductions in context.
-
How much of the total query count comes from batch-size estimation? Does the estimator usually process just one candidate, or are larger batches common?
Follow-up on Our Rebuttal
Dear Reviewer,
Thank you again for your careful and thoughtful review. We understand that this is a busy time, and as the discussion period is coming to a close, we wanted to briefly follow up. We hope our responses have adequately addressed your questions and concerns. If so, we would sincerely appreciate it if you could consider increasing your rating.
We would be very happy to provide any further clarification.
Best regards