Extending curvature to all submodular functions yields the first multiplicative greedy approximation guarantees that apply even when the function takes negative values.
hub Canonical reference
An analysis of approximations for maximizing submodular set functions—I.Mathematical Programming, 14(1):265–294
Canonical reference. 80% of citing Pith papers cite this work as background.
13
Pith papers citing it
2,925
external citations · Crossref
Background
80% of classified citations
hub tools
citation-role summary
background 4
method 1
citation-polarity summary
years
2026 13representative citing papers
A new algorithm finds a matroid basis in tilde O(n to the 3/7) adaptive rounds via independence oracle.
MechaRule localizes agonist neurons in LLMs via contrastive hierarchical ablation to ground rule extraction in circuitry, recalling 96.8% of high-effect neurons and reducing task performance when suppressed.
ContextualJailbreak uses evolutionary search over simulated primed dialogues with novel mutations to reach 90-100% attack success on open LLMs and transfers to some closed frontier models at 15-90% rates.
A covariance-adapting algorithm for semi-bandits achieves asymptotically tight regret bounds under a new sub-exponential distribution family, with direct application to sparse rewards.
The observability and controllability Gramians parameterized by sensor and actuator node subsets are determinantal point processes.
SeedER uses initial dense seeding followed by RL-driven selective expansion to improve recall on compositional KG queries while limiting candidate set size.
SkillLens organizes skills into policies-strategies-procedures-primitives layers, retrieves via degree-corrected random walk, and uses a verifier for local adaptation, yielding up to 6.31 pp gains on MuLocbench and raising ALFWorld success from 45% to 51.31%.
A reformulation of Bayesian OED as dense matrix subset selection plus a pipelined Schur-complement greedy algorithm on hundreds of GPUs enables optimization of 175-sensor networks for billion-degree-of-freedom tsunami models with near-perfect scaling.
A question-adaptive greedy frame selector combines SigLIP relevance and DINOv2 coverage under a submodular objective with a text classifier routing to preset trade-offs, yielding accuracy gains on MLVU especially at low frame budgets.
Revenue maximization for pricing datasets to budget-constrained buyers is APX-hard, with a 2-approximation for online arrivals and a (1-1/e)^{-1}-approximation for offline.
Selective prediction abstains unless all Lipschitz-consistent heads in the version space agree on a certified label for each pool point.
RCD balances relevance, coverage, and diversity in a knapsack-constrained selection framework, with experiments showing that selector choice and budget level determine optimal unitization strategies on clinical datasets.
citing papers explorer
-
Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
Extending curvature to all submodular functions yields the first multiplicative greedy approximation guarantees that apply even when the function takes negative values.
-
An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
A new algorithm finds a matroid basis in tilde O(n to the 3/7) adaptive rounds via independence oracle.
-
Neuron-Anchored Rule Extraction for Large Language Models via Contrastive Hierarchical Ablation
MechaRule localizes agonist neurons in LLMs via contrastive hierarchical ablation to ground rule extraction in circuitry, recalling 96.8% of high-effect neurons and reducing task performance when suppressed.
-
ContextualJailbreak: Evolutionary Red-Teaming via Simulated Conversational Priming
ContextualJailbreak uses evolutionary search over simulated primed dialogues with novel mutations to reach 90-100% attack success on open LLMs and transfers to some closed frontier models at 15-90% rates.
-
Covariance-adapting algorithm for semi-bandits with application to sparse rewards
A covariance-adapting algorithm for semi-bandits achieves asymptotically tight regret bounds under a new sub-exponential distribution family, with direct application to sparse rewards.
-
Connections Between Determinantal Point Processes and Gramians in Control
The observability and controllability Gramians parameterized by sensor and actuator node subsets are determinantal point processes.
-
SeedER: Seed-and-Expand Retrieval from Knowledge Graphs
SeedER uses initial dense seeding followed by RL-driven selective expansion to improve recall on compositional KG queries while limiting candidate set size.
-
SkillLens: Adaptive Multi-Granularity Skill Reuse for Cost-Efficient LLM Agents
SkillLens organizes skills into policies-strategies-procedures-primitives layers, retrieves via degree-corrected random walk, and uses a verifier for local adaptation, yielding up to 6.31 pp gains on MuLocbench and raising ALFWorld success from 45% to 51.31%.
-
Sensor Placement for Tsunami Early Warning via Large-Scale Bayesian Optimal Experimental Design
A reformulation of Bayesian OED as dense matrix subset selection plus a pipelined Schur-complement greedy algorithm on hundreds of GPUs enables optimization of 175-sensor networks for billion-degree-of-freedom tsunami models with near-perfect scaling.
-
Adaptive Greedy Frame Selection for Long Video Understanding
A question-adaptive greedy frame selector combines SigLIP relevance and DINOv2 coverage under a submodular objective with a text classifier routing to preset trade-offs, yielding accuracy gains on MLVU especially at low frame budgets.
-
Revenue-Optimal Pricing for Budget-Constrained Buyers in Data Markets
Revenue maximization for pricing datasets to budget-constrained buyers is APX-hard, with a 2-approximation for online arrivals and a (1-1/e)^{-1}-approximation for offline.
-
Selective Prediction from Agreement: A Lipschitz-Consistent Version Space Approach
Selective prediction abstains unless all Lipschitz-consistent heads in the version space agree on a certified label for each pool point.
-
Budget-Aware Routing for Long Clinical Text
RCD balances relevance, coverage, and diversity in a knapsack-constrained selection framework, with experiments showing that selector choice and budget level determine optimal unitization strategies on clinical datasets.