An analysis of approximations for maximizing submodular set functions—I

1978/12/01 by G. L. Nemhauser, George L. Nemhauser, L. A. Wolsey +3 · 301 citations
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation

paper · doi:10.1007/bf01588971

Cited by

• Pandemic monitoring with global aircraft-based wastewater surveillance networks
• Submodular maximization meets streaming: matchings, matroids, and more
• Multiobjective Optimization Using the R2 Utility
• Retain or Consolidate? Budget-Dependent Operator Selection for Language Agent Memory
• RUBRIC: Realism--Utility Balanced Ranking for Imbalanced Classification
• AIM-CoT: Active Information-driven Multimodal Chain-of-Thought for Vision-Language Reasoning
• Nyström Error Beyond M-Matrices: A Minimal Diagonally Dominant Obstruction
• The Shared Discovery Paradox: How a One-Answer Rule Turns Better Information into Worse Search
• Uncertainty-Aware Multi-Robot Task Allocation With Strongly Coupled Inter-Robot Rewards
• MinShap: A Shapley-Based Framework for Feature Redundancy
• Fast and Private Max-Sum Diversification
• When Is Heterogeneous Distance-Decay Facility Location Tractable? A Structural Classification, Exact Methods, and a Real-World Study
• CIPHER: A Decoupled Exploration-Selection Framework for Test-Time Scaling of Data Science Agents
• Accurate and Efficient Long-Term Memory for LLM Agents
• Multifidelity sensor placement in Bayesian state estimation problems
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• Information Decomposition Diagrams Applied beyond Shannon Entropy: A Generalization of Hu's Theorem
• A new system-wide diversity measure for recommendations with efficient algorithms
• An improved algorithm for the submodular secretary problem with a cardinality constraint
• An Efficient Randomized Algorithm for Rumor Blocking in Online Social Networks
• Bounded Degree Approximations of Stochastic Networks
• Greedy bi-criteria approximations for k-medians and k-means
• Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
• Tensor Learning-based Precoder Codebooks for FD-MIMO Systems
• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization
• Efficient Submodular Function Maximization under Linear Packing\n Constraints
• Constrained Submodular Maximization via a Non-symmetric Technique
• Graph Neural Networks for Decentralized Multi-Robot Submodular Action Selection
• DIVINE: Diverse Influential Training Points for Data Visualization and Model Refinement
• Algorithmic Meta-Theorems for Monotone Submodular Maximization
• Generating Discriminative Object Proposals via Submodular Ranking
• Sub-modularity and Antenna Selection in MIMO systems
• Influencer selection under budget constraints: a learning approach
• Social Networks and the Choices People Make
• New performance guarantees for the greedy maximization of submodular set\n functions
• Learning Optimal Classification Trees: Strong Max-Flow Formulations
• Almost Optimal Streaming Algorithms for Coverage Problems
• Active Learning for Autonomous Intelligent Agents: Exploration, Curiosity, and Interaction
• Gaussian Process Landmarking for Three-Dimensional Geometric Morphometrics
• Consistent Evidence, Robust Recognition: Faithful Attribution Regularization under Geometric Transformations
• On Optimal Approximations for k-Submodular Maximization via Multilinear Extension
• SpecAHD: Localize to Specialize for Automated Heuristic Design in Large-Scale Routing Problems
• Accelerated Experimental Design for Pairwise Comparisons
• FPT Approximation Schemes for Maximizing Submodular Functions
• FORGE: Frame Orthogonality in Relevance Geometry for Long-Form Video Understanding
• Efficient Online Conformal Selection with Limited Feedback
• Deletion-Robust Submodular Maximization at Scale
• Scalable Explanation of Inferences on Large Graphs
• Sensor Selection and Optimal Precision in\n \H₂/\H_\∞ Estimation Framework: Theory and\n Algorithms
• Fundamental Limits of Localization with Fluid Antenna Systems: A Fisher Information Analysis
• Strategic Server Deployment under Uncertainty in Mobile Edge Computing
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically\n Triggered Arms
• Resilient Monotone Submodular Function Maximization
• Learning to Optimize Tensor Programs
• Optimizing Offer Sets in Sub-Linear Time
• Structured Personalization: Modeling Constraints as Matroids for Data-Minimal LLM Agents
• Uncertainty-Aware Subset Selection for Robust Visual Explainability under Distribution Shifts
• Structured Learning of Two-Level Dynamic Rankings
• The FAST Algorithm for Submodular Maximization
• OptMap: Geometric Map Distillation via Submodular Maximization
• Promoting Fairness in Information Access within Social Networks
• Networked Restless Multi-Arm Bandits with Reinforcement Learning
• Network Structure Inference, A Survey: Motivations, Methods, and Applications
• VLM-Pruner: Buffering for Spatial Sparsity in an Efficient VLM Centrifugal Token Pruning Paradigm
• Knowledge Completion for Generics using Guided Tensor Factorization
• Soft Quality-Diversity Optimization
• Truthful and Trustworthy IoT AI Agents via Immediate-Penalty Enforcement under Approximate VCG Mechanisms
• Submodular Maximization Through Barrier Functions
• Bandit Guided Submodular Curriculum for Adaptive Subset Selection
• The Collapse of Patches
• Optimal experimental design for infinite-dimensional Bayesian inverse problems governed by PDEs: a review
• Cycle Cancellation for Submodular Fractional Allocations and Applications
• Efficient Greedy Algorithms for Feature Selection in Robot Visual Localization
• A Unified Framework of Constrained Robust Submodular Optimization with\n Applications
• Time-Critical Adversarial Influence Blocking Maximization
• Detecting Viruses in Contact Networks with Unreliable Detectors
• Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
• PIGEON: VLM-Driven Object Navigation via Points of Interest Selection
• Fast Semidifferential-based Submodular Function Optimization
• Non-Monotone Submodular Maximization with Multiple Knapsacks in Static\n and Dynamic Settings
• A fast and scalable computational framework for large-scale and high-dimensional Bayesian optimal experimental design
• Differentiable Greedy Submodular Maximization: Guarantees, Gradient Estimators, and Applications
• Fairness in Streaming Submodular Maximization: Algorithms and Hardness
• DynaAct: Large Language Model Reasoning with Dynamic Action Spaces
• Past-aware game-theoretic centrality in complex contagion dynamics
• Asymptotic Analysis of Objectives based on Fisher Information in Active Learning
• MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planning
• Robust Optimization for Non-Convex Objectives
• Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
• Rawlsian many-to-one matching with non-linear utility
• RobustFSM: Submodular Maximization in Federated Setting with Malicious Clients
• Information-theoretic minimax and submodular optimization algorithms for multivariate Markov chains
• Opinion Dynamics: A Comprehensive Overview
• FLoC: Facility Location-Based Efficient Visual Token Compression for Long Video Understanding
• A strong formulation for Multiple Allocation Hub Location based on supermodular inequalities
• Stochastic Conditional Gradient++
• Multiwinner Voting with Fairness Constraints
• Budget Feasible Mechanisms
• Deep Active Learning for Named Entity Recognition
• KGEval: Estimating Accuracy of Automatically Constructed Knowledge Graphs
• Achieving Fully Proportional Representation is Easy in Practice
• An Information-Theoretic Approach to PMU Placement in Electric Power Systems
• Variational Optimization for the Submodular Maximum Coverage Problem
• DUM: Diversity-Weighted Utility Maximization for Recommendations
• Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
• Submodular Optimization for Efficient Semi-supervised Support Vector Machines
• A Resource-Aware Approach to Collaborative Loop Closure Detection with Provable Performance Guarantees
• Practical and sample efficient zero-shot HPO
• Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization
• A maximal-coverage approach to prioritizing newborn sickle cell screening sites in Uganda using a sickle cell-malaria co-risk surface
• Resurrecting Submodularity for Neural Text Generation
• Learning From Less Data: Diversified Subset Selection and Active\n Learning in Image Classification Tasks
• Approximate Submodularity and Its Implications in Discrete Optimization
• Online Diverse Learning to Rank from Partial-Click Feedback
• Adaptive Cascade Submodular Maximization
• Continuous DR-submodular Maximization: Structure and Algorithms
• Determinantal Point Processes for Machine Learning
• Influence Function based Data Poisoning Attacks to Top-N Recommender Systems
• Consistent Nonparametric Different-Feature Selection via the Sparsest k-Subgraph Problem
• Defensive Resource Allocation in Social Networks
• On maximizing a monotone k-submodular function subject to a matroid constraint
• Resilient Active Target Tracking with Multiple Robots
• Sample Greedy Based Task Allocation for Multiple Robot Systems
• Submodular Maximization Meets Streaming: Matchings, Matroids, and More
• Block-Wise MAP Inference for Determinantal Point Processes with Application to Change-Point Detection
• Adaptive Submodular Optimization under Matroid Constraints
• Thresholded Covering Algorithms for Robust and Max-Min Optimization
• A Coordinated Search Strategy for Multiple Solitary Robots: An Extension
• Collaborative Scheduling of Time-dependent UAVs,Vehicles and Workers for Crowdsensing in Disaster Response
• Interpreting Black Box Predictions using Fisher Kernels
• Sum of Squares Submodularity
• Improving the betweenness centrality of a node by adding links
• Geometric Algorithms for Neural Combinatorial Optimization with Constraints
• Submodular Function Maximization via the Multilinear Relaxation and\n Contention Resolution Schemes
• Active Learning: Problem Settings and Recent Developments
• IMAS²: Joint Agent Selection and Information-Theoretic Coordinated Perception In Dec-POMDPs
• Supermodular Maximization with Cardinality Constraints
• Differentially Private Combinatorial Optimization
• LoRAverse: A Submodular Framework to Retrieve Diverse Adapters for Diffusion Models
• Market-Driven Subset Selection for Budgeted Training
• Robust Least Squares Problems with Binary Uncertain Data
• Failure-Driven Workflow Refinement
• Scalable Projection-Free Optimization
• Stability in Online Assignment Games
• Diversifying Seeds and Audience in Social Influence Maximization
• The Online Submodular Cover Problem
• Multi-fidelity Batch Active Learning for Gaussian Process Classifiers
• Prompt Optimization Across Multiple Agents for Representing Diverse Human Populations
• GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training
• A Possibility Frontier Approach to Diverse Talent Selection
• Robust Sensor Placement for Poisson Arrivals with False Alarm Aware Spatiotemporal Sensing
• Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time
• Non-submodular Visual Attention for Robot Navigation
• Looking Beyond the Known: Towards a Data Discovery Guided Open-World Object Detection
• Approximation Algorithms for D-optimal Design
• Submodular Context Partitioning and Compression for In-Context Learning
• Directed Information γ-covering: An Information-Theoretic Framework for Context Engineering
• A Greedy PDE Router for Blending Neural Operators and Classical Methods
• Constrained Monotone Function Maximization and the Supermodular Degree
• Diverse Trajectory Forecasting with Determinantal Point Processes
• Balancing Information Exposure in Social Networks
• SubZeroCore: A Submodular Approach with Zero Training for Coreset Selection
• Symmetry and approximability of submodular maximization problems
• Maximizing the Weighted Number of Spanning Trees: Near-t-Optimal Graphs
• Stochastic Path Planning in Correlated Obstacle Fields
• Distributed Rumor Blocking with Multiple Positive Cascades
• BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Task assignment optimization in knowledge-intensive crowdsourcing
• Submodular Inference of Diffusion Networks from Multiple Trees
• Finding Optimal Sinks for Random Walkers in a Network
• Online Combinatorial Optimization for Interconnected Refrigeration Systems: Linear Approximation and Submodularity
• Beyond pointwise submodularity: Non-monotone adaptive submodular maximization in linear time
• Near-Optimal Active Learning of Multi-Output Gaussian Processes
• Sensitivity Analysis of Submodular Function Maximization
• Complexes Detection in Biological Networks via Diversified Dense Subgraphs Mining
• On Budget-Feasible Mechanism Design for Symmetric Submodular Objectives
• Fractional 0-1 programming and submodularity
• Expedited Multi-Target Search with Guaranteed Performance via Multi-fidelity Gaussian Processes
• Pruning Random Forests for Prediction on a Budget
• Query-Focused Opinion Summarization for User-Generated Content
• Adaptive Submodular Meta-Learning
• Submodular Matroid Secretary Problem with Shortlists
• Fast Non-Monotone Submodular Maximisation Subject to a Matroid Constraint
• Regularized Submodular Maximization at Scale
• Sensor placement for fault location identification in water networks: A\n minimum test cover approach
• A Pressure-Based Diffusion Model for Influence Maximization on Social Networks
• On Maximization of Weakly Modular Functions: Guarantees of Multi-stage\n Algorithms, Tractability, and Hardness
• Regret Bounds for Gaussian-Process Optimization in Large Domains
• FemtoCaching: Wireless Video Content Delivery through Distributed\n Caching Helpers
• Stochastic Depletion Problems: Effective Myopic Policies for a Class of Dynamic Optimization Problems
• Using First Hitting Times to Find Sets that Maximize the Convergence Rate to Consensus
• Efficient Combinatorial Optimization for Word-level Adversarial Textual Attack
• Query Answering under Volume-Based Diversity Functions
• Exact Computation of Influence Spread by Binary Decision Diagrams
• ToMA: Token Merge with Attention for Diffusion Models
• Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets
• Diverse mini-batch Active Learning
• Online Myopic Network Covering
• Time-constrained Adaptive Influence Maximization
• Node-Constrained Traffic Engineering: Theory and Applications
• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
• Bayesian Budget Feasibility with Posted Pricing
• Interception in Distance-Vector Routing Networks
• GeoLayer: Towards Low-Latency and Cost-Efficient Geo-Distributed Graph Stores with Layered Graph
• Dependent Randomized Rounding for Matroid Polytopes and Applications
• Gaming and Cooperation in Federated Learning: What Can Happen and How to Monitor It
• Selecting Interlacing Committees
• Stability and Recovery for Independence Systems
• Nearly Linear Time Deterministic Algorithms for Submodular Maximization Under Knapsack Constraint and Beyond
• Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budget
• SIMILAR: Submodular Information Measures Based Active Learning In\n Realistic Scenarios
• Observability-driven Assignment of Heterogeneous Sensors for Multi-Target Tracking
• Matroid Bandits: Fast Combinatorial Optimization with Learning
• InSQuAD: In-Context Learning for Efficient Retrieval via Submodular Mutual Information to Enforce Quality and Diversity
• Adaptive Sampling for Fast Constrained Maximization of Submodular Function
• MMTok: Multimodal Coverage Maximization for Efficient Inference of VLMs
• Optimal Tagging with Markov Chain Optimization
• Incremental-Decremental Maximization
• Efficient Approximation Algorithms for Optimal Large-scale Network\n Monitoring
• CASPER: Concept-integrated Sparse Representation for Scientific Retrieval
• Resilient Non-Submodular Maximization over Matroid Constraints
• Linear-Time Algorithms for Adaptive Submodular Maximization
• Stochastic Depletion Problems: Effective Myopic Policies for a class of Dynamic Optimization Problems
• Scalable Greedy Feature Selection via Weak Submodularity
• EffiEval: Efficient and Generalizable Model Evaluation via Capability Coverage Maximization
• Feature Cross Search via Submodular Optimization
• Data-Efficient Biomedical In-Context Learning: A Diversity-Enhanced Submodular Perspective
• Scalable and Energy-Efficient Predictive Data Collection in Wireless Sensor Networks with Constructive Interference
• apricot: Submodular selection for data summarization in Python
• FPT-Algorithms for the ℓ-Matchoid Problem with a Coverage Objective
• Influence Maximization under The Non-progressive Linear Threshold Model
• Exploiting Mobility in Cache-Assisted D2D Networks: Performance Analysis and Optimization
• EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design
• Diversified Top-k Similarity Search in Large Attributed Networks
• Network Prebunking Problem: Optimizing Prebunking Targets to Suppress the Spread of Misinformation in Social Networks
• Optimization with Demand Oracles
• Combinatorial Approaches for Embedded Feature Selection in Nonlinear SVMs
• Performance Bounds for the k-Batch Greedy Strategy in Optimization Problems with Curvature
• On Misinformation Containment in Online Social Networks
• RANA: Robust Active Learning for Noisy Network Alignment
• Influence Maximization in Continuous Time Diffusion Networks
• Autonomous Exploration with Terrestrial-Aerial Bimodal Vehicles
• Almost Optimal Semi-streaming Maximization for k-Extendible Systems
• Optimal Algorithms for Submodular Maximization with Distributed Constraints
• Differentiable Greedy Networks
• HIAL: A New Paradigm for Hypergraph Active Learning via Influence Maximization
• Online Learning with Probing for Sequential User-Centric Selection
• DynamiQ: Planning for Dynamics in Network Streaming Analytics Systems
• Tree Space Prototypes: Another Look at Making Tree Ensembles Interpretable
• Non-monotone DR-submodular Maximization: Approximation and Regret Guarantees
• CrowdFusion: A Crowdsourced Approach on Data Fusion Refinement
• RCELF: A Residual-based Approach for Influence Maximization Problem
• Web Item Reviewing Made Easy By Leveraging Available User Feedback
• Stream Clipper: Scalable Submodular Maximization on Stream
• Online Learning of Independent Cascade Models with Node-level Feedback
• Mako: A Self-Evolving Agentic Operating System (SE-AOS) for Autonomous Web Exploitation
• Guaranteed Bounds for General Approximate Dynamic Programming
• PACMS: Submodular Context Selection as a Pluggable Engine for LLM Agents
• Deadline-Driven Multi-node Mobile Charging
• Subset Selection for Gaussian Markov Random Fields
• Failure-Resilient Coverage Maximization with Multiple Robots
• Multi-Robot Gaussian Process Estimation and Coverage: A Deterministic Sequencing Algorithm and Regret Analysis
• Modulo: Drive-by Sensing at City-scale on the Cheap
• Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
• Approximation Analysis of Influence Spread in Social Networks
• Truthful Mechanisms for Competing Submodular Processes
• Optimization of convergence rate via algebraic connectivity
• Randomized Composable Core-sets for Distributed Submodular Maximization
• Maximizing the Spread of Cascades Using Network Design
• CLAIM: Curriculum Learning Policy for Influence Maximization in Unknown Social Networks
• Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems
• Sensor placement minimizing the state estimation mean square error: Performance guarantees of greedy solutions
• ForestHash: Semantic Hashing With Shallow Random Forests and Tiny Convolutional Networks
• Influence Maximization With Deactivation In Social Networks
• Scalable Submodular Policy Optimization via Pruned Submodularity Graph
• Submodular Functions: from Discrete to Continous Domains
• An approximation algorithm for the link building problem
• Succinct Coverage Oracles
• Improving Attribution Methods by Learning Submodular Functions
• New Models and Methods for Formation and Analysis of Social Networks
• Adaptive Influence Maximization in Social Networks: Why Commit when You\n can Adapt?
• A Machine Learning Approach to Shipping Box Design
• Opinion Dynamics in Social Networks: A Local Interaction Game with Stubborn Agents
• Near-Optimally Teaching the Crowd to Classify
• On Approximating Partial Set Cover and Generalizations
• "Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack
• Competition analysis on the over-the-counter credit default swap market
• Achieving Fully Proportional Representation: Approximability Results
• A greedy anytime algorithm for sparse PCA
• Regularized Non-monotone Submodular Maximization
• Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets
• Coupon Advertising in Online Social Systems: Algorithms and Sampling Techniques
• Strategic Resource Allocation for Competitive Influence in Social\n Networks
• Exploiting Structure of Uncertainty for Efficient Matroid Semi-Bandits
• An Approximation Algorithm for Risk-averse Submodular Optimization
• Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments
• Learning to Select Base Classes for Few-shot Classification
• Tiering as a Stochastic Submodular Optimization Problem
• Streaming Algorithms for News and Scientific Literature Recommendation: Submodular Maximization with a d-Knapsack Constraint