- Rating
- 1
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper studies monotone submodular maximization with a knapsack and group cardinality lower/upper bounds. A minimum-cost fair base is augmented through addition and replacement operations. Duplicate pruning yields an auxiliary partition-matroid-plus-knapsack problem, and a best-of-base/decoded-solution argument converts an alpha approximation into alpha/(1+alpha). This gives an expected offline factor near 0.387. Invoking an imported streaming routine gives a claimed two-pass 1/(7+epsilon) approximation with O(K) memory. A separate density-truncated local search gives a multi-pass 1/(5+epsilon) guarantee. Experiments examine exact seed-quota feasibility, coverage utility, RR-estimated influence retention, memory, and runtime.
Critical strengths
-
The paper provides a clean exact-feasibility reduction. The objective h(M)=f(C union A(M))−f(C) remains monotone submodular despite replacements. Nonnegative operation costs and duplicate pruning permit a single partition matroid. Combining the auxiliary guarantee with the base solution gives the stated alpha/(1+alpha) transfer without relaxing group lower bounds.
-
The paper presents a multi-pass guarantee. The density invariant, budget-rejection certificate, and blockwise progress recurrence provide a self-contained path to the stronger auxiliary factor. Its singleton-scaled threshold grid and explicit zero-budget branch are valuable.
Critical weaknesses
-
This paper provides a delta-improvement over a known theoretical problem, while the applications of the problem are very limited.
-
Algorithm 4 removes prior threshold access using geometric copies, with a creation range involving singleton value divided by cost. These are distinct interfaces. The submission must justify total resources across copies and applicability to zero-cost auxiliary operations, rather than inherit the per-copy bounds directly. A legal instance makes the scope issue concrete: let one group contain c,e,g, all of weight 1, with lower quota 1, upper quota 2, budget 3, and f(S)=|S|. Any chosen base singleton c leaves residual budget 2; replacing c by e has operation weight 0 and auxiliary singleton value 1. A division-based unknown-threshold creation range is not finite on this input without an additional rule. Appendix B.3 fixes density-test evaluation by multiplication, but does not specify the finite threshold family or prove its total resource bound. The grid in Appendix B.2 is for the separate multi-pass algorithm after a singleton-estimation pass. Importing that grid does not automatically preserve the two-pass count.
-
The feasibility plots are useful checks, but the relaxed-lower-bound baseline and quota-free methods are not expected to meet the proposed exact constraints. The paper does include exactly feasible comparators, which deserve acknowledgment. Their main paired utility comparison, however, is on small two-group coverage instances whose construction is not fully specified. Figure 8 evaluates exactly feasible methods on Epinions/Pokec but reports time and oracle calls rather than paired influence. The LastFM/Twitch retention experiment does not sufficiently specify costs and quotas, and retention relative to one budget-only heuristic is not an optimum-relative guarantee. Thus the practical advantage under exact fairness is less well established than the feasibility result.
Questions for authors
- Which exact source result establishes Lemma 2.2 without knowing OPT_aux, with total O(K) memory and O(K) queries per operation across all threshold copies? Please provide the complete interface or an explicit adaptation and proof.
- For the zero-weight positive-value replacement above, how is a finite unknown-threshold family constructed? Which MatKnapStream version is implemented by TwoPass, and how are threshold estimation, copies, passes, and zero residual budget accounted for together?
- Please specify the coverage-instance construction and LastFM/Twitch costs and quotas, and report paired independent influence estimates for the exactly feasible Epinions/Pokec runs already used in Figure 8. How do the benefits change when oracle storage and preprocessing are included?
Thank you, Reviewer 3, for your feedback. We address your comments point by point below.
W1. We disagree with the characterization of our contribution as a delta-improvement given the gains in approximation and feasibility.
The expected offline approximation ratio improves from 0.241 [1] to about 0.387−O(ε). The two-pass ratio improves from 1/12−O(ε) [2] to 1/(7+ε). These are relative increases of about 61% and 71% in the respective constant terms. MultiPass achieves 1/(5+ε).
Our algorithms satisfy the budget and the fairness constraints. Cui et al. [2] relax each lower fairness constraint to ⌊ℓi/2⌋.
We believe the problem has broader applications. Submodular maximization is used in influence maximization [3], sensor placement [4], and document summarization [5]. The budgeted version with group constraints has been used for movie recommendation, image summarization, and social network coverage [2].
W2. We revised TwoPass in Section 4. The second pass uses the best feasible singleton value so far to update a finite set of thresholds. The density test uses multiplication to handle zero costs. Appendices A.9--A.10 give the proof and count all active copies.
W3. With the same budget and quotas, TwoPass and MultiPass average 96.67% and 97.04% coverage, versus 88.89% for FairBase+1Swap. Table 3 gives the paired comparison for the exactly feasible solutions in Figure 8. LastFM/Twitch retention is measured against a budget-only greedy heuristic.
Q1. Cui et al.'s Theorems 4.19 and 4.21 analyze Algorithm 3 with a fixed threshold. Appendices A.9--A.10 prove the revised bound with the threshold unknown. For fixed ε, all copies together use O(Klog(K+1)) working space and O(Klog(K+1)) queries per auxiliary operation.
Q2. Pass 1 builds the fair base. For R>0, pass 2 anchors a ratio-1+η grid at the first positive mt/R and keeps thresholds in [mt/(6R),Kmt/(ηR)]. Here mt is the best feasible singleton value so far and η=min{ε/6,1}. At R=0, one zero-threshold copy handles free operations. Appendix B.3 works through your example. Figure 8 used the original TwoPass, which required positive operation costs. Its threshold rule was adapted from Cui et al.'s Algorithm 4 in Appendix B, MatKnapStream (without pre-access to τ).
Q3. Appendix C describes the 18-vertex coverage template and its expansion, and gives the LastFM/Twitch costs and quotas. Table 3 reports the 150 original Figure 8 solutions scored on 200,000 RR sets per graph, independent of selection. Both methods gain about 0.28 percentage points over Cui+ExactRepair at Epinions budget 20. Cui+ExactRepair leads both at all five Pokec budgets. In the cached Epinions budget-20 replay (Table 4), including preparation and evaluation reduces MultiPass's time saving over Cui+ExactRepair from about 15% to 9%. Their parent-process peaks are 383 and 355 MB, respectively.
[1] Zhou et al. A Constant Approximation Algorithm for Fair Submodular Maximization under a Knapsack Constraint. Operations Research Letters, 2026.
[2] Cui et al. Fairness in Streaming Submodular Maximization Subject to a Knapsack Constraint. KDD, 2024.
[3] Kempe, Kleinberg, and Tardos. Maximizing the Spread of Influence through a Social Network. KDD, 2003.
[4] Krause, Singh, and Guestrin. Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies. JMLR, 2008.
[5] Lin and Bilmes. A Class of Submodular Functions for Document Summarization. ACL, 2011.