Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

No abstract is available for this paper.

• Publication year

  2011

• Venue

  SIAM journal on computing (Print)

• Publication date

  2011-11-01

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1137/080733991
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Maximizing Non-Monotone Submodular Functions

  2011cited by this paper
• A Threshold of ln(n) for approximating set cover

  2009influential reference
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

  2009cited by this paper
• Symmetry and Approximability of Submodular Maximization Problems

  2009cited by this paper
• Non-monotone submodular maximization under matroid and knapsack constraints

  2009cited by this paper
• Maximizing submodular set functions subject to multiple linear constraints

  2009cited by this paper
• Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions

  2008cited by this paper
• On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP

  2008cited by this paper
• Optimal approximation for the submodular welfare problem in the value oracle model

  2008influential reference
• Revisiting the Greedy Approach to Submodular Set Function Maximization

  2007cited by this paper
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)

  2007influential reference
• Greedy in Approximation Algorithms

  2006cited by this paper
• On the complexity of approximating k-set packing

  2006cited by this paper
• Tight approximation algorithms for maximum general assignment problems

  2006influential reference
• Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e

  2006influential reference
• Dependent rounding and its applications to approximation algorithms

  2006influential reference
• On maximizing welfare when utility functions are subadditive

  2006cited by this paper
• An improved approximation algorithm for combinatorial auctions with submodular bidders

  2006cited by this paper
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

  2005cited by this paper
• A recursive greedy algorithm for walks in directed graphs

  2005cited by this paper
• Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions

  2005influential reference
• A note on maximizing a submodular set function subject to a knapsack constraint

  2004influential reference
• The Probabilistic Method: Alon/Probabilistic Method

  2004cited by this paper
• Maximum Coverage Problem with Group Budget Constraints and Applications

  2004cited by this paper
• Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee

  2004influential reference
• Combinatorial optimization. Polyhedra and efficiency.

  2003influential reference
• Distributions on level-sets with applications to approximation algorithms

  2001influential reference
• Combinatorial auctions with decreasing marginal utilities

  2001cited by this paper
• Submodular Functions, Matroids, and Certain Polyhedra

  2001cited by this paper
• A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time

  2000cited by this paper
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions

  2000cited by this paper
• A PTAS for the multiple knapsack problem

  2000cited by this paper
• The Budgeted Maximum Coverage Problem

  1999cited by this paper
• The Probabilistic Method

  1998cited by this paper
• A New Approximation Algorithm for Finding Heavy Planar SubgraphsGruia C alinescu

  1997cited by this paper
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• A personal communication

  1989cited by this paper
• Testing membership in matroid polyhedra

  1984cited by this paper
• An analysis of the greedy algorithm for the submodular set covering problem

  1982influential reference
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems

  1982influential reference
• Note--On "Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms"

  1979influential reference
• An analysis of approximations for maximizing submodular set functions—I

  1978influential reference
• An Analysis of the Greedy Heuristic for Independence Systems

  1978cited by this paper
• Best Algorithms for Approximating the Maximum of a Submodular Set Function

  1978cited by this paper
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms

  1977cited by this paper
• ON A COMBINATORIAL

  year unknowncited by this paper

• The Distortion of Prior-Independent b-Matching Mechanisms

  2026cites this paper
• Streaming Stochastic Submodular Maximization with On-Demand User Requests

  2026cites this paper
• Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy

  2026cites this paper
• Efficient Algorithms for the Interval Maximum Coverage Problem

  2026cites this paper
• Bicriteria Algorithms for Submodular Cover with Partition and Fairness Constraints

  2026cites this paper
• Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization

  2026cites this paper
• Computing Approximate Pareto Frontiers for Submodular Utility and Cost Tradeoffs

  2026cites this paper
• $\gamma$-weakly $\theta$-up-concavity: Linearizable Non-Convex Optimization with Applications to DR-Submodular and OSS Functions

  2026cites this paper
• Dimension-Free Correlated Sampling for the Hypersimplex

  2025influential citation
• An approximation algorithm for mobile multi-agent monitoring and routing problem

  2025cites this paper
• Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes

  2025influential citation
• Maximizing a $ k $-submodular function with $ p $-system constraints

  2025cites this paper
• Adaptive Conditional Gradient Descent

  2025influential citation
• Submodular Maximization Subject to Uniform and Partition Matroids: From Theory to Practical Applications and Distributed Solutions

  2025cites this paper
• Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints

  2025cites this paper
• A prophet inequality based approach to the adaptive ProbeTopK\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{K

  2025cites this paper
• Fair Submodular Maximization over a Knapsack Constraint

  2025influential citation
• Adaptivity Gaps for Stochastic Probing with Subadditive Functions

  2025cites this paper
• Maximization of k-Submodular Function with d-Knapsack Constraints Over Sliding Window

  2025cites this paper
• Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps

  2025cites this paper
• Dynamic Algorithms for Submodular Matching

  2025cites this paper
• Logarithmic Approximations for Fair k-Set Selection

  2025cites this paper
• Discrepancy And Fair Division For Non-Additive Valuations

  2025cites this paper
• Clustered Control of Transition-Independent MDPs

  2025cites this paper
• Fixed-Parameter Tractable Submodular Maximization over a Matroid

  2025cites this paper
• Monotone submodular maximization under the pairwise capacity constraint

  2025cites this paper
• MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planning

  2025cites this paper
• Supermodular Maximization with Cardinality Constraints

  2025cites this paper
• Max-Cut with Multiple Cardinality Constraints

  2025influential citation
• A Unified Approach to Submodular Maximization Under Noise

  2025cites this paper
• Adaptive Threshold Sampling for Pure Exploration in Submodular Bandits

  2025influential citation
• Weak submodularity implies localizability: Local search for constrained non-submodular function maximization

  2025cites this paper
• Offline and Online Distributed Submodular Maximization under a Partitioned Matroid Constraint

  2025cites this paper
• Maximization of DR-Submodular Regularization Under Convex Constraints: A Study of Bi-Factor Approximation Algorithms

  2025cites this paper
• Cycle Cancellation for Submodular Fractional Allocations and Applications

  2025cites this paper
• Deep Non-monotone Submodular Network: An Application to Conditional Video Summarization

  2025influential citation
• Stochastic Submodular Data Forgetting

  2025cites this paper
• Gödel Test: Can Large Language Models Solve Easy Conjectures?

  2025cites this paper
• Submodular + Supermodular function maximization with knapsack constraint

  2025cites this paper
• Partitioning and Observability in Linear Systems via Submodular Optimization

  2025influential citation
• Dynamic Stepsize Techniques in DR-Submodular Maximization

  2025cites this paper
• A Systematic Review and Evolutionary Analysis of the Optimization Techniques and Software Tools in Hybrid Microgrid Systems

  2025cites this paper
• An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale

  2025cites this paper
• Randomized approximation algorithms for monotone k-submodular function maximization with constraints

  2025cites this paper
• Semantic-Conditional Network for Micro-Video Summarization

  2025cites this paper
• Diverse Committees with Incomplete or Inaccurate Approval Ballots

  2025cites this paper
• RobustFSM: Submodular Maximization in Federated Setting with Malicious Clients

  2025cites this paper
• Fair and Reliable Reconnections for Temporary Disruptions in Electric Distribution Networks

  2025cites this paper
• Robust Least Squares Problems with Binary Uncertain Data

  2025cites this paper
• Constrained Assortment Optimization under the Mixed-Logit Model: Approximation Schemes and Outer Approximation Approaches

  2025cites this paper
• Lower Bounds for Weighted Matroid Problems

  2025cites this paper
• Generalized Concentration-Based Performance Guarantees on Sensor Selection for State Estimation

  2025cites this paper
• Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budget

  2025cites this paper
• The Power of Mediators: Price of Anarchy and Stability in Bayesian Games with Submodular Social Welfare

  2025cites this paper
• The Submodular Santa Claus Problem

  2024cites this paper
• Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions

  2024cites this paper
• Cuts in Graphs with Matroid Constraints

  2024cites this paper
• On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP

  2024cites this paper
• Uncovering Sets of Maximum Dissimilarity on Random Process Data

  2024cites this paper
• Fast deterministic algorithms for non-submodular maximization with strong performance guarantees

  2024cites this paper
• Revisiting stochastic submodular maximization with cardinality constraint: A bandit perspective

  2024influential citation
• Fractional Budget Allocation for Influence Maximization under General Marketing Strategies

  2024cites this paper
• Submodular Maximization in Exactly n Queries

  2024cites this paper
• How Interpretable Are Interpretable Graph Neural Networks?

  2024cites this paper
• Evolving Reliable Differentiating Constraints for the Chance-constrained Maximum Coverage Problem

  2024cites this paper
• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization

  2024cites this paper
• Harm Mitigation in Recommender Systems under User Preference Dynamics

  2024influential citation
• Communication- and Computation-Efficient Distributed Decision-Making in Multi-Robot Networks

  2024cites this paper
• Subquadratic Submodular Maximization with a General Matroid Constraint

  2024cites this paper
• From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization

  2024cites this paper
• Public Event Scheduling with Busy Agents

  2024cites this paper
• Finding Effective Ad Allocations: How to Exploit User History

  2024cites this paper
• A Semi-streaming Algorithm for Monotone Regularized Submodular Maximization with a Matroid Constraint

  2024cites this paper
• On contention resolution for the hypergraph matching, knapsack, and k-column sparse packing problems

  2024cites this paper
• On Bounds for Greedy Schemes in String Optimization based on Greedy Curvatures

  2024cites this paper
• The Average-Value Allocation Problem

  2024influential citation
• Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints

  2024cites this paper
• Learning decision catalogues for situated decision making: The case of scoring systems

  2024cites this paper
• Deep Submodular Peripteral Networks

  2024cites this paper
• Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint

  2024cites this paper
• Mini-batch Submodular Maximization

  2024influential citation
• Collecting LoRa Data with an Energy-Budgeted UAV: A Bi-Criteria Approximate Solution

  2024cites this paper
• Geometric Covering via Extraction Theorem

  2024cites this paper
• The Forward-Reverse Greedy Algorithm for Distributed Submodular Maximization

  2024cites this paper
• Diversity-aware clustering: Computational Complexity and Approximation Algorithms

  2024cites this paper
• Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization

  2024cites this paper
• Is Limited Information Enough? An Approximate Multi-agent Coverage Control in Non-Convex Discrete Environments

  2024cites this paper
• Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks

  2024cites this paper
• View-based Explanations for Graph Neural Networks (Extended Abstract)

  2024cites this paper
• Learning Set Functions with Implicit Differentiation

  2024cites this paper
• Decomposable Submodular Maximization in Federated Setting

  2024influential citation
• Distributed Experimental Design Networks

  2024cites this paper
• Greedy algorithms for stochastic monotone k-submodular maximization under full-bandit feedback

  2024cites this paper
• Online Matroid Intersection: Submodular Water-Filling and Matroidal Welfare Maximization

  2024cites this paper
• Differentiable Extensions with Rounding Guarantees for Combinatorial Optimization over Permutations

  2024cites this paper
• Observability and Generalized Sensor Placement for Nonlinear Quality Models in Drinking Water Networks

  2024cites this paper
• Hybrid Regret Minimization: A Submodular Approach

  2024cites this paper
• Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint

  2024cites this paper
• Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms

  2024cites this paper
• A fast algorithm for maximizing monotone non-submodular functions

  2024cites this paper