- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The submitted paper studies the problem of maximizing a monotone submodular function subject to a matroid constraint in a fully dynamic setting (the stream contains insertions and deletions).
The approximation guarantee achieved is with poly logarithmic in n and the rank k amortized update time.
This is the first work to get a constant guarantee with polylogarithmic amortized update time.
Critical strengths
The strength of the paper is in the result, polylogarthmic update time is the ultimate goal and this is the first paper to achieve that goal (albeit in an amortized setting).
Critical weaknesses
It is not a strict improvement on prior work. First the guarantee is amortized whereas the work of Banihashem et al (2024) is an "each update" guarantee. Furthermore, there update guarantee is independent of the ground set n (and, less importantly, has a logarithmic dependency on the parameter).
The paper would benefit from a clearer explanation what the value/new insights are. The guarantee 1/4 appears frequently in these papers, as they follow the (great) paper of Chakrabarti & Kale, and apart from that, several techniques that appear in other papers are combined, such as sampling from a pool set of candidates and different levels of refinement with (different frequencies in their update schedule).
Questions for authors
The paper contains the full pseudo-code of the algorithms which is good. However, I think it would be helpful if the authors in addition clarify more what the new ideas are (especially compared to prior work). What should we take away from the submitted paper apart from the improved amortized guarantee?
Also, how good are these algorithms compared to other ones in a more practical scenario? There is no implementation and experiments, so it is unclear how the complexity and hidden constants behave compared to other approaches. This strenghtens the importance of the first point. If the main contribution is theoretical, then it is should emphasize what the novelty in terms of ideas and technics are.
Thank you for your helpful feedback. We clarify our contributions and present new experiments.
1. Theoretical contributions
Comparison with prior guarantees. We agree that our result does not uniformly improve upon Banihashem et al. (2024). Their query guarantee holds in expectation for each update, is independent of n, and has only logarithmic dependence on 1/ϵ. Our guarantee is amortized: the total query bound holds for every realization of the randomness, but individual updates may be expensive. We trade additional dependence on n and 1/ϵ for eliminating the polynomial dependence on the matroid rank. We will make these distinctions explicit in the comparison.
We view the technical contribution in two parts.
Polylogarithmic maintenance of the streaming swap process. Dynamic maintenance of swaps was already studied by Dütting et al. (2023). Our observation is that these exchange decisions admit efficient batch maintenance. We use their circuit group-testing method (Lemma 5.4) to find the lightest exchangeable element with O(log(2k)) independence queries. During an uninterrupted reconstruction, marginal gains decrease and failed exchange tests remain valid, allowing many acceptances to be processed without a full rescan after each one. This is an observation about the compatibility of established techniques; the exchange rule and circuit-search primitive are inherited.
Simpler and quicker. We believe the cardinality frameworks of Lattanzi et al. (2020, revised 2023) and Banihashem et al. (2023) also offer routes to a polylogarithmic dynamic matroid algorithm with a 1/4−ϵ approximation. We verified the former's main approximation and query-analysis steps in a model allowing queries on deleted elements; the latter remains a possibility. The former uses sampling robustness and cross-level charging for deletion-triggered rebuilds; the latter estimates sample counts and analyzes random depth. Our construction avoids sample-size estimation and random-depth analysis by coupling exact truncation with a fixed rebuilding schedule. Each optimum-value guess maintains O(logn) time levels storing snapshots and small residuals; reconstruction inherits the parent state and processes its residual plus recent insertions. Within a reconstruction, marginal buckets classify candidates; a random-permutation scan and binary searches determine the retained acceptance prefix exactly. Fixed depth and rebuilt suffixes make our algorithm and analysis more intuitive: costs follow rebuild frequencies; a deletion-tolerant exchange certificate bounds approximation loss. For fixed ϵ and k≤n, our query bound also matches or improves the upper bounds of these cardinality algorithms.
2. Experimental evaluation
We added preliminary experiments on Enron, an email network dataset, to our theoretical study as reviewers suggested, comparing with Dütting et al. (2023) and Banihashem et al. (2024).
Setup. We uniformly sampled 4,096 candidates without replacement and randomly split them into eight equal synthetic groups, each with capacity k/8, giving a rank-k partition matroid. The objective counts nodes covered by selected candidates' closed neighborhoods among all 36,692 graph nodes. Candidates, groups and arrival order are fixed across ranks and methods. All methods use full parallel guesses and native ϵ=0.1 (not identical approximation guarantees); three seeds per configuration give 45 runs.
FIFO stream. Starting empty, insert 1,024 candidates. For each remaining candidate, insert it, then delete the oldest live candidate as a separate update, maintaining an output after each (live size 1,025 then 1,024). Finally delete all remaining candidates in arrival order: 8,192 updates, one insertion/deletion per candidate.
Results. Each cell gives mean value-plus-independence queries/update over the full stream / mean solution value over the 6,145 updates with 1,024 or 1,025 live candidates.
Observations. Solution values are similar. We use 58.5%/85.4% fewer queries than Dütting et al. (2023) at k=64/128, but more at smaller ranks. Our query ratio to Banihashem et al. (2024) falls from 40.84 to 3.25, still above one. At fixed accuracy, their bounds have quadratic/linear rank factors up to logs; our polylogarithmic bound replaces the latter's k by ϵ−1log(2k)log(2n). As expected, our relative query cost improves as k grows. Rebuttal time limited completed runs to k≤128; we will complete larger-rank experiments to further demonstrate our query advantage.