acceptodds
Under review as a conference paper at ICLR 2027

Improved Streaming Fair Submodular Maximization under a Knapsack Constraint: Application to Budgeted Fair Influence Maximization

Abstract

Given a ground set partitioned into groups , we seek a subset maximizing a monotone submodular function , subject to a knapsack constraint and fairness constraints for every group , with particular focus on the streaming setting. This problem arises in many applications, such as budgeted fair influence maximization in social networks. We propose an operation-based reduction method which yields a approximation, improving the previous best guarantee 0.241 in Zhou et al. (2026). Moreover, we give the first constant-factor streaming approximations that satisfy both the knapsack constraint and all fairness constraints exactly. The previous best streaming result (Cui et al., 2024) achieves an approximation ratio of while relaxing each fairness lower bound to . Our two-pass algorithm improves the ratio to using memory, where . We further propose a new technique called density-truncated local search, which achieves a approximation using passes and memory. Experiments on budgeted fair influence maximization over real-world social networks show that our algorithms maintain exact feasibility in all runs while achieving competitive influence spread. Additional evaluations show that our algorithms retain over 96% of the influence spread that can be achieved by a greedy method without considering fairness.

Primary area:
optimization
Keywords:
submodular maximization, streaming algorithm, fairness, knapsack, influence maximization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_PNgqOpenReview ↗
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
  1. 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.

  2. 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
  1. This paper provides a delta-improvement over a known theoretical problem, while the applications of the problem are very limited.

  2. 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.

  3. 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
  1. 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.
  2. 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?
  3. 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?
1 comment

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.2410.241 [1] to about 0.387−O(ε)0.387-O(\varepsilon). The two-pass ratio improves from 1/12−O(ε)1/12-O(\varepsilon) [2] to 1/(7+ε)1/(7+\varepsilon). These are relative increases of about 61% and 71% in the respective constant terms. MultiPass achieves 1/(5+ε)1/(5+\varepsilon).

Our algorithms satisfy the budget and the fairness constraints. Cui et al. [2] relax each lower fairness constraint to ⌊ℓi/2⌋\lfloor\ell_i/2\rfloor.

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 ε\varepsilon, all copies together use O(Klog⁡(K+1))O(K\log(K+1)) working space and O(Klog⁡(K+1))O(K\log(K+1)) queries per auxiliary operation.

Q2. Pass 1 builds the fair base. For R>0R>0, pass 2 anchors a ratio-1+η1+\eta grid at the first positive mt/Rm_t/R and keeps thresholds in [mt/(6R),Kmt/(ηR)][m_t/(6R),Km_t/(\eta R)]. Here mtm_t is the best feasible singleton value so far and η=min⁡{ε/6,1}\eta=\min\{\varepsilon/6,1\}. At R=0R=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 τ\tau).

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.

Reviewer_67T7OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors develop algorithms for Fair Submodular Maximization under Knapsack constraints (FSMK). In this problem, the ground set is partitioned into several groups, with given upper and lower cardinality bounds for each group. A feasible solution respects these bounds for each partition, and a global knapsack constraint.

The first algorithm in the paper is an offline algorithm where we create an initial solution with minimum-weight items to satisfy the lower bounds for each group. Then we reduce to ordinary constrained submodular maximization by an instance which contains only addition or replacement operations. The authors additionally provide this algorithm in the form of a 2-pass streaming algorithm, where the submodular maximization subroutine on the reduced instance is replaced by a weaker 1-pass algorithm. Finally, they also introduce a stronger multi-pass local search algorithm.

Critical strengths

The authors address an important problem, improve upon guarantees of the prior work in several settings, and especially also manage to exactly satisfy the group cardinality and knapsack constraints. The authors also provide an experimental evaluation that showcases exactly this point as an advantage over prior work. The algorithms are overall clean, and the paper is well written.

Critical weaknesses

The algorithmic contribution is limited, as the algorithms are mostly simple reductions or applications of existing frameworks. There is no central strong algorithmic idea.

  1. The idea of the first algorithm to satisfy the lower group cardinality bounds via the smallest weight instances, and then apply known algorithms for knapsack and partition-matroid constrained submodular maximization. However, this can't recover the 1-1/e approximation of either the group cardinality or knapsack constraint. The authors also do not provide any lower bounds showing that this approach would be ideal. Not that this would be necessary, but it shows that the algorithm probably leaves potential value on the table.

  2. The 2-pass streaming algorithm just swaps out the subroutine for constrained submodular maximization of the previous approach.

  3. The local search algorithm is essentially the multi-pass matroid local search algorithm of Huang et al. (2020), adapted to a knapsack constraint via density thresholds. But the main problem is that the Huang paper isn't mentioned in the paper in connection with it's algorithmic ideas. The authors should also make it explicit which ideas are their own versus which ideas are from prior work.

The experiments do not show the method of Zhou et al. (2026) even though the authors claim to beat it. The offline algorithm is never run. Finally, a fair comparison with Cui et al could showcase a pareto trade-off between fairness violation and objective value (or showing some aggregate of the group cardinality bound violations of Cui et al. and compare it to the output of this paper's algorithms, but with the cardinality bounds sufficiently relaxed to match the violation of the Cui et al. algorithm)

Questions for authors

Are you aware of any (non-obvious) lower bounds for FSMK? Do you think that your results are optimal?

1 comment

Thank you, Reviewer 2, for your feedback. We address your comments point by point below.

W1. Section 3 uses a minimum-cost fair base, one partition matroid, and a residual knapsack. Pruning duplicate introductions preserves auxiliary value and allows decoding under the original constraints. Taking the better of the base and the decoded solution transfers α\alpha to α/(1+α)\alpha/(1+\alpha).

Appendix A.20 discusses the special cases. Sviridenko gives 1−1/e1-1/e for a knapsack alone. With only group quotas, we can optimize under the upper quotas and fill deficient groups without losing value, retaining the expected 1−1/e1-1/e matroid guarantee.

W2. TwoPass reuses the reduction. Section 4 builds the fair base in pass 1, then generates operations and updates the threshold window as candidates arrive in pass 2.

W3. Section 5 now credits Huang et al.\ for the exchange framework used in MultiPass. We analyze how density screening and the budget constraint affect the exchanges. A budget rejection certifies a lower bound on the returned value. Without such a rejection, blockwise charging gives a progress recurrence. Together these cases give a 1/(4+ε)1/(4+\varepsilon)-approximation for the auxiliary problem.

W4. Thank you for the suggestion. Our experiments focus on evaluating the streaming algorithms.

In Appendix C we match each group's shortfall by setting its lower quota to min⁡{4,ci}\min\{4,c_i\}, where cic_i is raw FairKnapStream's count. Budget, upper quotas, and order stay fixed. Across 15 paired runs, the original TwoPass and MultiPass average 96.67% and 97.04% coverage, versus 80.00% for Cui. Each wins 14 pairs and ties one.

Q1. Appendix A.20 embeds Maximum kk-Cover using one group, unit costs, and ℓ1=u1=B=k\ell_1=u_1=B=k. Padding to kk preserves coverage, so Feige's 1−1/e1-1/e hardness threshold applies to offline FSMK. Our guarantee remains below that threshold, and the optimal ratio for the general problem is open.

Reviewer_FtQFOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies monotone submodular maximization under a knapsack budget and lower and upper quotas for disjoint groups. It constructs a minimum-cost fair base and encodes subsequent choices as additions or replacements. The resulting auxiliary problem has a monotone submodular objective, a partition matroid, and a residual knapsack constraint. An α\alpha-approximation transfers to an α/(1+α)\alpha/(1+\alpha) guarantee for the original problem. This yields an offline ratio of approximately 0.387, a two-pass ratio of 1/(7+ε)1/(7+\varepsilon), and, using a new density-truncated local search, a 1/(5+ε)1/(5+\varepsilon) ratio in O(1/ε)O(1/\varepsilon) passes, all with exact feasibility. Experiments evaluate influence maximization and additional coverage instances.

Critical strengths
  1. The reduction addresses the structural obstacle clearly. Lower quotas destroy downward-closedness. Encoding operations relative to the cheapest fair base restores a standard auxiliary feasible family, while evaluating h(M)=f(C∪A(M))−f(C)h(M)=f(C\cup A(M))-f(C) preserves monotonicity and submodularity. The duplicate-pruning, feasibility, optimal-benchmark, and value-transfer arguments fit together convincingly. This is a reusable contribution, and exact lower quotas are materially stronger than the relaxed guarantees of earlier streaming work.

  2. The multi-pass analysis provides an additional technical contribution. The budget-rejection case supplies a value certificate, while the no-rejection case uses blockwise charging and a progress recurrence. The slot argument in the proof of Lemma 5.4 and the handling of zero residual budget make the analysis reasonably complete.

Critical weaknesses
  1. The practical benefit is less established than the theoretical improvement. The strongest utility comparison against exactly feasible competitors uses small coverage instances whose construction is not specified clearly. Real-network feasibility and retention relative to a budget-only heuristic answer different questions; they do not show a utility advantage over exactly feasible methods on those same networks. The “over 96%” result is relative to a heuristic and should not be interpreted as a general small cost of fairness. A matched spread-versus-resource comparison on Epinions and Pokec would make the practical contribution more convincing.

  2. The streaming resource claims need to be interpreted at the implementation level. The model streams candidate seeds and assumes value-oracle access to a fixed network; the reported stored-item counts exclude the oracle. Each candidate generates up to L+1L+1 operations, and the multi-pass algorithm can require 42 passes at ε=0.1\varepsilon=0.1. Appendix C reports substantial logical oracle counts, identifies TwoPass as the slowest compared implementation, and shows MultiPass becoming slower than Cui+ExactRepair at larger budgets. These are useful results, but deserve more prominence. The large retained-item counts relative to KK also call for an explanation of accuracy-dependent constants and what is being counted; they do not by themselves contradict an O(K)O(K) bound for fixed accuracy. These limitations affect the practical significance without invalidating the theoretical contribution.

Questions for authors
  1. How are the additional coverage instances generated? On the same Epinions/Pokec instances used for timing, what spread do the proposed methods achieve relative to Cui+ExactRepair and FairBase+1Swap, with independent evaluation samples?

  2. Does the implementation use the full stated pass count and threshold grid? Please explain the stored-item counts, report peak bytes with and without the RR oracle, and clarify how logical oracle calls map to actual work. This would help assess the operational benefit of the candidate-stream model.

  3. How does the auxiliary 1/(4+ε)1/(4+\varepsilon) multi-pass result compare with prior streaming algorithms for a partition matroid plus a knapsack? Also, what sampling accuracy is needed to transfer the exact-oracle approximation guarantee to expected influence when using a fixed RR sample? Exact feasibility is unaffected, but the objective guarantee needs this distinction.

2 comments

Thank you, Reviewer 1, for your feedback. We address your comments point by point below.

W1. On LastFM and Twitch, we report how much spread our methods retain compared with a greedy method that only enforces the budget. On Epinions and Pokec, Table 3 compares spread with Cui+ExactRepair and FairBase+1Swap under the same budget and group quotas.

W2. Figure 8 shows that MultiPass selects faster than Cui+ExactRepair at budgets 20 and 40 on both graphs. Cui+ExactRepair is faster at larger budgets. TwoPass is the slowest.

Q1. Each vertex of an 18-vertex directed template is copied 112, 140, or 168 times. Each arc expands to all arcs between the corresponding sets of copies. A seed covers its out-neighbors. Appendix C gives the costs, budget 8, and bounds [4,5][4,5] for each of the two groups.

Table 3 uses the 150 Figure 8 solutions from the original TwoPass, MultiPass, and Cui+ExactRepair, plus one FairBase+1Swap solution per graph and budget. We score all solutions on 200,000 common RR sets per graph, independent of selection. TwoPass and MultiPass have higher mean spread than both baselines at Epinions budgets 20 and 40. Both baselines lead at the other Epinions budgets and all Pokec budgets.

Q2. At ε=0.1\varepsilon=0.1, MultiPass ran the full grid of 132--215 thresholds and all 42 passes (two setup scans and 40 local-search scans). The original TwoPass ran two passes and used 536--801 live copies at peak. Each candidate gives up to L+1L+1 operations, and storage counts entries across copies. MultiPass's logical queries include tests skipped by caching and pruning.

In the Epinions budget-20 replay, parent-process peaks with cached RR data were 368,312,320, 383,238,144, and 354,516,992 bytes for TwoPass, MultiPass, and Cui+ExactRepair (Table 4). After preloading, MultiPass and Cui+ExactRepair allocated up to 6.29 and 7.88 MB in Python during selection. The TwoPass allocation trace timed out. Process peaks without the RR oracle were not measured.

Q3. For a partition matroid plus a knapsack, Cui et al. (Theorem 4.21) give a 1/[6(1+η)]1/[6(1+\eta)] approximation in one pass with a suitable threshold. On the same problem, our MultiPass achieves a 1/(4+ε)1/(4+\varepsilon) approximation in O(1/ε)O(1/\varepsilon) passes.

Appendix C gives the RR bound. For MM feasible seed sets, log⁡(2M/δ)/(2a2)\log(2M/\delta)/(2a^2) independent selection samples give uniform normalized error at most aa with probability at least 1−δ1-\delta. On this event, an empirical factor ρ\rho gives true normalized spread at least ρp(O)−(1+ρ)a\rho p(O)-(1+\rho)a, where p(O)p(O) is the optimal normalized spread. For randomized guarantees the bound holds in conditional expectation. If 0<b≤p(O)0<b\le p(O), taking a=ξb/(1+ρ)a=\xi b/(1+\rho) gives factor ρ−ξ\rho-\xi.

Thank you for the clarifications.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.