Scalable Submodular Policy Optimization via Pruned Submodularity Graph

Aditi Anand; Dildar Ali; Suman Banerjee

REVIEW 4 major objections 5 minor 32 references

Scalable Submodular Policy Optimization via Pruned Submodularity Graph

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A pruned submodularity graph lets policy-gradient reinforcement learning handle submodular rewards at scale, the paper argues.

desk verdict New combination, but the core promise is unproven: the pruning step never connects to the gradient estimator, and the constant-factor guarantee is asserted without proof and collides with the paper's own inapproximability theorem. read the letter →

arxiv 2507.13834 v1 pith:S7EJSVBF submitted 2025-07-18 cs.LG cs.AIcs.MA

Aditi Anand , Suman Banerjee , Dildar Ali This is my paper · ORCID

classification cs.LGcs.AIcs.MA

keywords submodularrewardreinforcementlearningpolicygradientprunedsubmodularitygraphstatespacereductiondiminishingreturnsfunctionmaximization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to extend reinforcement learning from additive rewards to submodular rewards, where the law of diminishing returns governs the objective. It proposes SGPO, a policy-gradient method that builds a weighted submodularity graph over visited states and prunes the states with the smallest divergence scores before estimating the gradient. The intended payoff is a scalable optimizer that still yields an approximate optimal policy, with a claimed constant-factor guarantee under simplified assumptions. Experiments across continuous and discrete environments report that SGPO collects more reward than an existing submodular RL baseline and shows smoother policy and critic loss curves.

What carries the argument

The submodularity graph is a weighted directed graph on the set of visited states, with edge weight $w_{uv} = F(v\mid u) - F(u\mid V\setminus\{u\})$ measuring how much value $v$ can add beyond what $u$ already contributes. Each state's divergence from a sampled set $U$ is $w_{U,v} = \min_{u\in U} w_{uv}$, and states with the smallest divergence are pruned as redundant. The argument is carried by the interaction between this pruning loop and the policy-gradient estimator of Theorem 3, which expresses $\nabla_\theta J(\pi_\theta)$ as an expectation over trajectories of $\sum_{i=0}^{H-1} \nabla_\theta \log \pi_\theta(a_i\mid s_i)\bigl(\sum_{j=i}^{H-1} R(s_{j+1}\mid \tau_{0:j}) + R(s_0)\bigr)$.

What would settle it

Run SGPO on one of the tested environments with pruning disabled and with increasing pruning aggressiveness $c$, then compare the expected return and the angle between the pruned and full-trajectory gradient estimates; if the difference grows without bound as $c$ increases, the pruning premise fails. Concretely, if the cosine similarity between $\nabla_\theta J$ computed on the full state set and on the pruned set $V'$ falls below 0.9 across epochs, the pruned gradient is not a faithful surrogate.

Watch

Extended reading notes

Core claim

The paper asserts that states visited during a submodular RL episode can be treated as a ground set, organized into a submodularity graph, and aggressively pruned without losing the information needed for policy improvement. The remaining states feed a policy-gradient estimator, derived in Theorem 3, that rewrites the submodular trajectory reward as a telescoping sum of marginal gains. SGPO then performs regularized gradient ascent on this estimate. The paper further asserts that this pruning makes the time and space cost manageable while preserving approximation quality, claiming a constant-factor approximation under simplified assumptions; its Theorem 2 simultaneously states that no polynomial-time algorithm can achieve a constant factor on general instances, where only logarithmic approximation is possible.

Load-bearing premise

The argument depends on the assumption that states with the smallest divergence score carry little policy-gradient information, so discarding them does not distort the gradient estimate used to update the policy.

Editorial extensions

If this is right

If the pruning premise holds, submodular objectives such as coverage, informative path planning, and entropy maximization become practical targets for policy-gradient RL at state-space sizes where full-trajectory evaluation is too costly.
The stated time bound $O(N n^4 s^2 m^2)$ and space bound $O(n^2)$ imply that the computational bottleneck is the graph construction and gradient estimator, not the number of states that survive pruning.
If the simplified-assumption constant-factor claim is correct, there is a class of submodular MDPs on which SGPO comes within a fixed multiplicative factor of the optimal policy, despite the general problem being logarithmically inapproximable.
The smoother policy- and critic-loss curves reported for SGPO suggest that pruning also acts as a variance-reduction mechanism during training, not merely as a computational shortcut.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the constant-factor statement in Section 5 and Theorem 2's logarithmic hardness bound are compatible only if the simplified assumptions exclude the hard instances; spelling out those assumptions would turn the pruning rule from an empirical recipe into a provable method.
Editorial inference: the divergence score could be reused outside submodular RL, for example to choose which transitions to store in a replay buffer or which states to use for value-function regression in standard RL pipelines.
Editorial inference: a natural stress test is to run SGPO on a submodular maximization instance with a known optimal solution and compare the achieved return against the $(1-1/e)$ greedy benchmark; the paper does not report such a calibration.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: the paper combines a pruned submodularity graph (Zhou et al.) with a policy gradient update for submodular RL. That combination is new, I think, but the advertised payoff—a provable approximation guarantee—is nowhere on the page. The conclusion says SGPO achieves a constant-factor guarantee 'under simplified assumptions,' yet no such theorem appears and Theorem 2 states constant-factor approximation is impossible for the general problem. So either the assumptions are doing all the work and need to be stated and proven, or the claim is false.

What it does well: the idea of using the pruning graph to reduce the state space in a submodular MDP is a reasonable engineering move and is grounded in existing literature [31]. Theorem 2, the inapproximability result for submodular RL, is a useful negative result to have, even if the proof is only sketched. Theorem 3 is a standard REINFORCE-style identity; for Markovian policies the reward-to-go form is fine because dropped past-reward terms have zero expectation. The experiments, while limited to one baseline, at least cover both continuous and discrete environments and show SGPO consistently above SubPO in the reported numbers.

Now the soft spots, in order of severity. First, the missing link between the pruning rule and the gradient estimator. Algorithm 1 drops states with small divergence w_{U,v} and builds the update set K only from survivors. Theorem 3's estimator sums score terms over all time steps of a full trajectory; using only surviving steps changes the estimate, and no bias bound or importance correction is given. That is a real gap: in policy gradients, omitting score terms is generically biased. So as written, SGPO is a heuristic, not a provable method. Second, the constant-factor claim. It appears only in the conclusion, with no statement of the assumptions and no proof; this is not a small omission. Third, the experiments have no error bars, no code or data, and only one baseline; Figures are hard to read. Hyperparameters r=c=8 are stated but not studied. Fourth, the writing and notation are rough (e.g., space complexity typed as 'O(n2) time', missing symbols, inconsistent use of V and Z). These are fixable but add up.

Who is this for? Someone already working on submodular RL who wants a quick heuristic for state pruning might find the empirical comparison mildly interesting. It is not yet at the standard of a research preprint claiming a proof.

My recommendation: don't send this to peer review in its current form. The core claim is unproven, the algorithm lacks a correctness argument, and the empirical work is too thin. If the authors add a real theorem about the pruning bias (or a counterexample showing where it fails) and clean up the claims and experiments, the idea could be worth another look.

Referee Report

4 major / 5 minor

Summary. The paper studies reinforcement learning with a submodular reward function and proposes an algorithm, SGPO, that prunes states using a pruned submodularity graph, then applies a policy gradient update on the remaining states. The authors claim a performance guarantee, give a complexity analysis, and report experiments on continuous and discrete environments comparing SGPO to SubPO. The central advertised result, however, is a constant-factor approximation guarantee that appears only in the concluding section without proof, and the algorithm's pruning step is never shown to preserve the gradient signal used in the update.

Significance. If the central claims were supported, the paper would contribute a scalable method for submodular RL with a provable approximation ratio, a problem class that has received little attention. The experimental comparison with SubPO and the use of a pruning technique from submodular maximization are potentially useful. However, the load-bearing theoretical statements are either unproved or in tension with the paper's own Theorem 2, and the algorithmic modification relative to standard policy gradient is not justified. As it stands, SGPO is presented as a heuristic with an unsupported guarantee, so the significance of the claimed contribution is not established.

major comments (4)

[Section 3, Algorithm 1 (lines 11-20) and Theorem 3 (Eq. 9)] No result connects the pruned set V' to the gradient estimator in Theorem 3. Theorem 3 (Eq. 9) is derived for full trajectories τ drawn from f(τ;π_θ), with a sum over every time step i=0,...,H-1. Algorithm 1 constructs K (line 20) only from states that survive the submodularity-graph pruning, so time steps whose states are pruned lose their score terms. The paper does not provide an unbiasedness proof, an importance-weighting scheme, or a bias bound relating the pruned estimator to ∇_θ J(π_θ). Consequently, the parameter update in Eq. 4 is a heuristic unless this gap is filled.
[Section 5, Concluding Remarks] The sentence 'We show that the proposed SGPO will achieve a constant factor approximation guarantee under the simplified assumptions' is not supported by any theorem or proof in the manuscript, and the 'simplified assumptions' are never stated. Moreover, Theorem 2 asserts that no polynomial-time algorithm can guarantee a constant-factor approximation for general SubRL; without an explicit articulation of which assumptions are relaxed and how they circumvent Theorem 2, the claimed guarantee is both unproved and in direct tension with the paper's own inapproximability result.
[Section 3, Theorem 2] The proof of Theorem 2 is not a rigorous reduction. It states a reduction from Group Steiner Tree to Submodular Orienteering and then to SubRL, but it does not specify the Submodular MDP states, actions, transition probabilities, or horizon in a way that makes the optimal policy value correspond to the optimal SOP walk. In particular, the SubRL formulation has time-augmented states (S = V × H) and stochastic transitions, while the claimed equivalence uses a deterministic walk with a budget constraint; no argument shows that maximizing the expected submodular reward over policies equals maximizing the set function over feasible walks. As stated, the theorem is unsubstantiated, and its interaction with the concluding constant-factor guarantee is never resolved.
[Section 3, Theorem 3 proof (Eqs. 20-22)] The transition from Eq. (20) to Eq. (22) drops the marginal-gain terms with j < i without stating the standard conditional-zero-expectation argument. That argument, which relies on the future action a_i being independent of past rewards conditioned on the prefix, is not given; without it the equality in Eq. (22) is not immediate. Additionally, the definition of R(τ) over trajectories that include actions is inconsistent with the formal definition R: 2^S → R for S = V × H, since a trajectory contains action symbols. These issues affect the correctness of the gradient estimator as presented, although they might be fixable with added assumptions and a standard derivation.

minor comments (5)

[Abstract and Section 1] The abstract and introduction state that the proposed approach 'provides a provably approximate solution,' but no theorem in the paper actually proves an approximation guarantee for SGPO; this wording should be revised to match the proven content.
[Section 3, Algorithm 1 description] The notation in line 15, w_{U,v} ← min_{u∈U} [R(v|u) − R(u|V \ {u})], uses R(v|u) without defining the marginal gain notation for a set function R; the standard notation Δ(v|u) = R(u ∪ {v}) − R(u) should be introduced earlier.
[Section 3, Complexity Analysis] In the complexity paragraph, 'To store the edges of the graph, it will take O(n^2) time' should read 'O(n^2) space,' and the expression O(H(sm) · H(sm) · H(n)) is not defined; the symbols H, s, m, and n are overloaded with the horizon H and the state/action dimensions, making the analysis hard to follow.
[Section 4, Table 1 and Figure 1] Some equations in Table 1, such as the GP(M) objective T(τ) = Σ_s w_s − λ Σ_s N_s, are ambiguous about the index of summation, and Figure 1 has multiple panels labeled (k) and (ℓ) that are not all referenced in the text, which complicates interpreting the reported results.
[Throughout] The paper repeatedly uses 'R' both for the reward function and for the set of rewards stored in Algorithm 1 (line 7), which is confusing; a different symbol, such as W or Q, would clarify the presentation.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction: the policy-gradient theorem is derived self-containedly and the pruning rule comes from external work; the unsupported approximation guarantee is a soundness gap, not circularity.

full rationale

The central derivation chain is self-contained. Theorem 3 (Eq. 9) is proved from the definition of J(pi_theta) in Eq. 2 via the log-derivative trick; it does not assume the pruning rule, the SGPO algorithm, or any of the paper's conclusions. The pruning construction in Algorithm 1 is inherited from the external method of Zhou et al. [31], and the authors' own prior works [1,2] appear only as background in the hyperparameter-sensitivity paragraph ('as informed by prior work on submodular maximization [1,2,31]'); they are not used to justify the gradient estimator or the approximation guarantee. The real weaknesses are soundness gaps rather than circularity: no lemma connects the pruned state set V' in Algorithm 1, line 20, to the full-trajectory estimator of Theorem 3, and Section 5's claim 'We show that the proposed SGPO will achieve a constant factor approximation guarantee under the simplified assumptions' is asserted without proof and is in tension with Theorem 2. These are missing derivations, not reductions of a result to its own inputs by construction. Accordingly, no specific circular step is identified; the only minor note is the non-load-bearing self-citation in the hyperparameter discussion.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The algorithm's usefulness depends on the unproven premise that pruning states by divergence preserves the gradient signal; the reward functions in the experiments contain hand-chosen constants (lambda, 9.965784) that are not justified; and the hardness result relies on a sketched reduction from Group Steiner Tree through Submodular Orienteering.

free parameters (5)

r = 8
Sampling parameter: number of states sampled per iteration is r times log n; chosen empirically in Section 3 based on performance in preliminary experiments.
c = 8
Pruning parameter: fraction of states removed per iteration is (1 - 1/sqrt(c)); chosen empirically in Section 3.
alpha
Regularization coefficient in the policy update Equation 4; value is not specified in the paper.
lambda
Penalty coefficient in the MuJoCo Ant and Graph-based M reward functions in Table 1; value is not specified.
constant 9.965784 = 9.965784
Added to entropy rewards in Table 1; the source or justification is not explained, so it appears chosen by hand to shape the reward scale.

assumptions (4)

ad hoc to paper Pruning states with low divergence w_{U,v} from the submodularity graph preserves the policy gradient signal.
Algorithm 1 lines 11-19 remove states with smallest divergence; no proof links this to the gradient estimator in Theorem 3.
domain assumption The reward function R is submodular over states and R(tau) can be decomposed as telescoping marginal gains with respect to the trajectory order.
Used in Theorem 3 expansion; this holds for any set function under the trajectory definition, not specifically as a consequence of submodularity.
domain assumption The reduction from Group Steiner Tree to Submodular Orienteering to SubRL in Theorem 2 is valid.
The reduction is only sketched; the SOP to SubRL step relies on unspecified details of policy randomization and expectation.
standard math NP is not contained in ZTIME(n polylog n).
Standard complexity assumption underlying the hardness statement in Theorem 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Scalable Submodular Policy Optimization via Pruned Submodularity Graph." pith.science (2026). https://pith.science/paper/S7EJSVBF

@misc{pith2026250713834,
  author       = {Pith},
  title        = {Pith review of: Scalable Submodular Policy Optimization via Pruned Submodularity Graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S7EJSVBF}},
  note         = {Machine review of arXiv:2507.13834}
}

read the original abstract

In Reinforcement Learning (abbreviated as RL), an agent interacts with the environment via a set of possible actions, and a reward is generated from some unknown distribution. The task here is to find an optimal set of actions such that the reward after a certain time step gets maximized. In a traditional setup, the reward function in an RL Problem is considered additive. However, in reality, there exist many problems, including path planning, coverage control, etc., the reward function follows the diminishing return, which can be modeled as a submodular function. In this paper, we study a variant of the RL Problem where the reward function is submodular, and our objective is to find an optimal policy such that this reward function gets maximized. We have proposed a pruned submodularity graph-based approach that provides a provably approximate solution in a feasible computation time. The proposed approach has been analyzed to understand its time and space requirements as well as a performance guarantee. We have experimented with a benchmark agent-environment setup, which has been used for similar previous studies, and the results are reported. From the results, we observe that the policy obtained by our proposed approach leads to more reward than the baseline methods.

Figures

Figures reproduced from arXiv: 2507.13834 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 28 canonical work pages

[31]

In: Artificial Intelligence and Statistics

Zhou, T., Ouyang, H., Bilmes, J., Chang, Y., Guestrin, C.: Scaling submodu- lar maximization via pruned submodularity graphs. In: Artificial Intelligence and Statistics. pp. 316–324. PMLR (2017)

work page 2017
[1]

In: International Conference on Advanced Data Mining and Applications

Ali, D., Banerjee, S., Prasad, Y.: Influential billboard slot selection using pruned submodularity graph. In: International Conference on Advanced Data Mining and Applications. pp. 216–230. Springer (2022)

work page 2022
[2]

Influential Billboard Slot Selection using Spatial Clustering and Pruned Submodularity Graph

Ali, D., Banerjee, S., Prasad, Y.: Influential billboard slot selection using spa- tial clustering and pruned submodularity graph. arXiv preprint arXiv:2305.08949 (2023)

work page Pith review arXiv 2023
[3]

Advances in Neural Information Processing Systems 30 (2017)

Bian, A., Levy, K., Krause, A., Buhmann, J.M.: Continuous dr-submodular max- imization: Structure and algorithms. Advances in Neural Information Processing Systems 30 (2017)

work page 2017
[4]

In: Proceedings eighth IEEE international conference on computer vision

Boykov, Y.Y., Jolly, M.P.: Interactive graph cuts for optimal boundary & region segmentation of objects in nd images. In: Proceedings eighth IEEE international conference on computer vision. ICCV 2001. vol. 1, pp. 105–112. IEEE (2001)

work page 2001
[5]

Mathematical Programming154, 225–247 (2015)

Chakrabarti, A., Kale, S.: Submodular maximization meets streaming: matchings, matroids, and more. Mathematical Programming154, 225–247 (2015)

work page 2015
[6]

Advances in Neural Information Processing Systems29 (2016)

Dolhansky, B.W., Bilmes, J.A.: Deep submodular functions: Definitions and learn- ing. Advances in Neural Information Processing Systems29 (2016)

work page 2016
[7]

Springer (2020)

Dong, H., Dong, H., Ding, Z., Zhang, S., Chang, T.: Deep Reinforcement Learning. Springer (2020)

work page 2020

Show all 32 references

[8]

a survey

Dughmi, S.: Submodular functions: Extensions, distributions, and algorithms. a survey. arXiv preprint arXiv:0912.0322 (2009)

2009 arXiv
[9]

Journal of Algorithms37(1), 66–84 (2000)

Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group steiner tree problem. Journal of Algorithms37(1), 66–84 (2000)

2000
[10]

European Journal of Oper- ational Research 255(2), 315–332 (2016)

Gunawan, A., Lau, H.C., Vansteenwegen, P.: Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Oper- ational Research 255(2), 315–332 (2016)

2016
[11]

arXiv preprint arXiv:2101.08763 (2021)

Honysz, P.J., Buschjäger, S., Morik, K.: Gpu-accelerated optimizer-aware evalua- tion of submodular exemplar clustering. arXiv preprint arXiv:2101.08763 (2021)

2021 arXiv
[12]

Ad- vances in neural information processing systems29 (2016)

Horel, T., Singer, Y.: Maximization of approximately submodular functions. Ad- vances in neural information processing systems29 (2016)

2016
[13]

In: Proceedings of the ninth ACM SIGKDD international confer- ence on Knowledge discovery and data mining

Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international confer- ence on Knowledge discovery and data mining. pp. 137–146 (2003)

2003
[14]

Tractability3(71- 104), 3 (2014) Anand et al

Krause, A., Golovin, D.: Submodular function maximization. Tractability3(71- 104), 3 (2014) Anand et al

2014
[15]

arXiv preprint arXiv:1207.1394 (2012)

Krause, A., Guestrin, C.E.: Near-optimal nonmyopic value of information in graph- ical models. arXiv preprint arXiv:1207.1394 (2012)

2012 arXiv
[16]

Journal of Machine Learning Research 9(2) (2008)

Krause, A., Singh, A., Guestrin, C.: Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research 9(2) (2008)

2008
[17]

SIAM Journal on Discrete Mathematics 23(4), 2053–2078 (2010)

Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM Journal on Discrete Mathematics 23(4), 2053–2078 (2010)

2010
[18]

In: Berkhin, P., Caruana, R., Wu, X

Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J.M., Glance, N.S.: Cost-effective outbreak detection in networks. In: Berkhin, P., Caruana, R., Wu, X. (eds.) Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,...
[19]

Transportation research part B: methodological171, 29–43 (2023)

Li, R., Mehr, N., Horowitz, R.: Submodularity of optimal sensor placement for traffic networks. Transportation research part B: methodological171, 29–43 (2023)

2023
[20]

In: Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies

Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies. pp. 510–520 (2011)

2011
[21]

The Journal of Machine Learning Research17(1), 8330–8373 (2016)

Mirzasoleiman, B., Karbasi, A., Sarkar, R., Krause, A.: Distributed submodular maximization. The Journal of Machine Learning Research17(1), 8330–8373 (2016)

2016
[22]

Mathematical programming14, 265–294 (1978)

Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions—i. Mathematical programming14, 265–294 (1978)

1978
[23]

arXiv preprint arXiv:2307.13372 (2023)

Prajapat, M., Mutn` y, M., Zeilinger, M.N., Krause, A.: Submodular reinforcement learning. arXiv preprint arXiv:2307.13372 (2023)

2023 arXiv
[24]

Advances in Neural Information Processing Sys- tems 35, 14998–15012 (2022)

Prajapat, M., Turchetta, M., Zeilinger, M., Krause, A.: Near-optimal multi-agent learning for safe coverage control. Advances in Neural Information Processing Sys- tems 35, 14998–15012 (2022)

2022
[25]

In: International Conference on Machine Learning

Sharma, D., Kapoor, A., Deshpande, A.: On greedy maximization of entropy. In: International Conference on Machine Learning. pp. 1330–1338. PMLR (2015)

2015
[26]

Singh, A., Krause, A.R., Guestrin, C., Kaiser, W.J., Batalin, M.: Efficient planning of informative paths for multiple robots (2006)

2006
[27]

of: Proceedings of the Second International CSP Solver Competition pp

Streeter, M., Golovin, D., Smith, S.F.: Combining multiple constraint solvers: Re- sults on the cpai’06 competition data. of: Proceedings of the Second International CSP Solver Competition pp. 11–18 (2008)

2008
[28]

In: 2017 IEEE 56th Annual Conference on De- cision and Control (CDC)

Sun, X., Cassandras, C.G., Meng, X.: A submodularity-based approach for multi- agent optimal coverage problems. In: 2017 IEEE 56th Annual Conference on De- cision and Control (CDC). pp. 4082–4087. IEEE (2017)

2017
[29]

A Bradford Book (2018)

Sutton, R.S.: Reinforcement learning: An introduction. A Bradford Book (2018)

2018
[30]

SIAM Journal on Discrete Mathematics33(3), 1452–1471 (2019)

Yoshida, Y.: Maximizing a monotone submodular function with a bounded curva- ture under a knapsack constraint. SIAM Journal on Discrete Mathematics33(3), 1452–1471 (2019)

2019
[2007]

pp. 420–429. ACM (2007)

2007

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [31]

In: Artificial Intelligence and Statistics

Zhou, T., Ouyang, H., Bilmes, J., Chang, Y., Guestrin, C.: Scaling submodu- lar maximization via pruned submodularity graphs. In: Artificial Intelligence and Statistics. pp. 316–324. PMLR (2017)

work page 2017

[2] [1]

In: International Conference on Advanced Data Mining and Applications

Ali, D., Banerjee, S., Prasad, Y.: Influential billboard slot selection using pruned submodularity graph. In: International Conference on Advanced Data Mining and Applications. pp. 216–230. Springer (2022)

work page 2022

[3] [2]

Influential Billboard Slot Selection using Spatial Clustering and Pruned Submodularity Graph

Ali, D., Banerjee, S., Prasad, Y.: Influential billboard slot selection using spa- tial clustering and pruned submodularity graph. arXiv preprint arXiv:2305.08949 (2023)

work page Pith review arXiv 2023

[4] [3]

Advances in Neural Information Processing Systems 30 (2017)

Bian, A., Levy, K., Krause, A., Buhmann, J.M.: Continuous dr-submodular max- imization: Structure and algorithms. Advances in Neural Information Processing Systems 30 (2017)

work page 2017

[5] [4]

In: Proceedings eighth IEEE international conference on computer vision

Boykov, Y.Y., Jolly, M.P.: Interactive graph cuts for optimal boundary & region segmentation of objects in nd images. In: Proceedings eighth IEEE international conference on computer vision. ICCV 2001. vol. 1, pp. 105–112. IEEE (2001)

work page 2001

[6] [5]

Mathematical Programming154, 225–247 (2015)

Chakrabarti, A., Kale, S.: Submodular maximization meets streaming: matchings, matroids, and more. Mathematical Programming154, 225–247 (2015)

work page 2015

[7] [6]

Advances in Neural Information Processing Systems29 (2016)

Dolhansky, B.W., Bilmes, J.A.: Deep submodular functions: Definitions and learn- ing. Advances in Neural Information Processing Systems29 (2016)

work page 2016

[8] [7]

Springer (2020)

Dong, H., Dong, H., Ding, Z., Zhang, S., Chang, T.: Deep Reinforcement Learning. Springer (2020)

work page 2020