Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search

We present an optimal, combinatorial $1-1/e$ approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm [G. Calinescu et al., IPCO, Springer, Berlin, 2007, pp. 182--196] our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by a local search. Both phases are run not on the actual objective function, but on a related auxiliary potential function, which is also monotone and submodular. In our previous work on maximum coverage [Y. Filmus and J. Ward, FOCS, IEEE, Piscataway, NJ, 2012, pp. 659--668], the potential function gives more weight to elements covered multiple times. We generalize this approach from coverage functions to arbitrary monotone submodular functions. When the objective function is a coverage function, both definitions of the potential function coincide. Our approach generalizes to the case where the monotone submodular function has restricted curvature. For any curvatu...

• Publication year

  2012

• Venue

  SIAM journal on computing (Print)

• Publication date

  2012-04-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/130920277arXiv 1204.4526
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Submodular Maximization with Cardinality Constraints

  2014cited by this paper
• Fast algorithms for maximizing submodular functions

  2014cited by this paper
• Tight Bounds for Submodular and Supermodular Optimization with Bounded Curvature

  2013cited by this paper
• Oblivious and Non-oblivious Local Search for Combinatorial Optimization

  2012cited by this paper
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

  2012cited by this paper
• I and J

  2012influential reference
• A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint

  2012cited by this paper
• The Power of Local Search: Maximum Coverage over a Matroid

  2012influential reference
• A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems

  2011cited by this paper
• Submodular function maximization via the multilinear relaxation and contention resolution schemes

  2011cited by this paper
• Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract)

  2011cited by this paper
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

  2011cited by this paper
• Maximizing Non-Monotone Submodular Functions

  2011cited by this paper
• A Unified Continuous Greedy Algorithm for Submodular Maximization

  2011influential reference
• Improved Approximations for k-Exchange Systems - (Extended Abstract)

  2011cited by this paper
• Submodularity and Curvature: The Optimal Algorithm

  2010cited by this paper
• Submodular maximization by simulated annealing

  2010cited by this paper
• Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures

  2010cited by this paper
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

  2009influential reference
• Non-monotone submodular maximization under matroid and knapsack constraints

  2009cited by this paper
• Submodularity and curvature : the optimal algorithm

  2008influential reference
• 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)

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

  2004cited by this paper
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP

  2002cited by this paper
• The Budgeted Maximum Coverage Problem

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

  1996cited by this paper
• An improved approximation ratio for the minimum latency problem

  1996cited by this paper
• On syntactic versus computational views of approximability

  1994cited by this paper
• New Local Search Approximation Techniques for Maximum Generalized Satisfiability Problems

  1994cited by this paper
• An analysis of approximations for maximizing submodular set functions—I

  1978influential reference
• Best Algorithms for Approximating the Maximum of a Submodular Set Function

  1978cited by this paper
• Matroids and the greedy algorithm

  1971cited by this paper
• Comments on bases in dependence structures

  1969cited by this paper
• Note on Independence Functions

  1957cited by this paper
• An algorithm for quadratic programming

  1956cited by this paper
• Sur la représentation approchée d'une fonction par des fractions rationnelles

  year unknowncited by this paper

• Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes

  2025cites this paper
• A Unified Approach to Submodular Maximization Under Noise

  2025cites this paper
• Weak submodularity implies localizability: Local search for constrained non-submodular function maximization

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

  2025cites this paper
• Tri-Ring: Asynchronous Service Provisioning with Online Learning in Edge Cloud Networks

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

  2025cites this paper
• A Kernelization Algorithm for Finding a Perfect Phylogeny From Mixed Tumor Samples

  2025cites this paper
• Limiting Disease Spreading in Human Networks

  2025cites this paper
• Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint

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

  2024cites this paper
• An Improved Genetic Algorithm for Set Cover using Rosenthal Potential

  2024cites this paper
• Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization

  2024cites this paper
• Fair Representation in Submodular Subset Selection: A Pareto Optimization Approach

  2024cites this paper
• Optimal study designs for cluster randomised trials: An overview of methods and results

  2023cites this paper
• A Primal-Dual Analysis of Monotone Submodular Maximization

  2023cites this paper
• Parameterized Matroid-Constrained Maximum Coverage

  2023cites this paper
• Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid

  2023cites this paper
• Matroid-Constrained Vertex Cover

  2023cites this paper
• Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits

  2023cites this paper
• $k$-Submodular Maximization with a Knapsack Constraint and $p$ Matroid Constraints

  2023cites this paper
• Result diversification with negative type distances by multi-objective evolutionary algorithms

  2023influential citation
• On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints

  2023cites this paper
• Jointly Optimal Routing and Caching with Bounded Link Capacities

  2023cites this paper
• Evaluation of combinatorial optimisation algorithms for c-optimal experimental designs with correlated observations

  2022cites this paper
• Practical Budgeted Submodular Maximization

  2022cites this paper
• Online Caching Networks with Adversarial Guarantees

  2022cites this paper
• Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function

  2022influential citation
• Maximizing Modular plus Non-monotone Submodular Functions

  2022cites this paper
• Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case

  2022cites this paper
• Optimal Utility Design of Greedy Algorithms in Resource Allocation Games

  2022cites this paper
• Approximate c-Optimal Experimental Designs with Correlated Observations using Combinatorial Optimisation

  2022cites this paper
• Maximizing a non-decreasing non-submodular function subject to various types of constraints

  2022cites this paper
• Efficient Submodular Optimization under Noise: Local Search is Robust

  2022cites this paper
• A Local Search-Based Approach for Set Covering

  2022cites this paper
• Greedy is Good: Constrained Non-submodular Function Maximization via Weak Submodularity

  2022cites this paper
• Greedy Guarantees for Non-submodular Function Maximization Under Independent System Constraint with Applications

  2022cites this paper
• FPT-Algorithms for the (cid:96) -Matchoid Problem with a Coverage Objective

  2022cites this paper
• Continuous Submodular Maximization: Boosting via Non-oblivious Function

  2022influential citation
• Online Caching Networks with Adversarial Guarantees

  2021cites this paper
• On Submodular Contextual Bandits

  2021cites this paper
• FPT-Algorithms for the ℓ -Matchoid Problem with a Coverage Objective

  2021cites this paper
• Streaming Submodular Maximization Under Matroid Constraints

  2021influential citation
• Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint

  2021cites this paper
• The Multi-budget Maximum Weighted Coverage Problem

  2021cites this paper
• A Simple Bound for Resilient Submodular Maximization with Curvature

  2021cites this paper
• On Optimal Approximations for $k$-Submodular Maximization via Multilinear Extension

  2021cites this paper
• Streaming Submodular Maximization with Matroid and Matching Constraints

  2021cites this paper
• Siting renewable power generation assets with combinatorial optimisation

  2021cites this paper
• Deterministic approximation algorithm for submodular maximization subject to a matroid constraint

  2021cites this paper
• Cache Networks of Counting Queues

  2021cites this paper
• Stochastic greedy algorithms for maximizing constrained submodular + supermodular functions

  2021cites this paper
• Two-stage submodular maximization problem beyond nonnegative and monotone

  2021cites this paper
• FPT-Algorithms for the l-Matchoid Problem with Linear and Submodular Objectives

  2020cites this paper
• Non-monotone submodular function maximization under k-system constraint

  2020cites this paper
• An Adaptive Algorithm for Maximization of Non-submodular Function with a Matroid Constraint

  2020cites this paper
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective

  2020cites this paper
• Robust Assignment Using Redundant Robots on Transport Networks With Uncertain Travel Time

  2020cites this paper
• Ranking an Assortment of Products via Sequential Submodular Optimization

  2020cites this paper
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

  2020cites this paper
• User-centric Optimization of Caching and Recommendations in Edge Cache Networks

  2020cites this paper
• Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions

  2020cites this paper
• Algorithmic Aspects in Information and Management: 14th International Conference, AAIM 2020, Jinhua, China, August 10–12, 2020, Proceedings

  2020influential citation
• A General Framework for Fairness in Multistakeholder Recommendations

  2020cites this paper
• Theory and Applications of Models of Computation: 16th International Conference, TAMC 2020, Changsha, China, October 18–20, 2020, Proceedings

  2020cites this paper
• Planning with Submodular Objective Functions

  2020cites this paper
• Non-Submodular Streaming Maximization with Minimum Memory and Low Adaptive Complexity

  2020cites this paper
• Approximation Guarantees for Deterministic Maximization of Submodular Function with a Matroid Constraint

  2020cites this paper
• Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint

  2019cites this paper
• Beyond submodular maximization via one-sided smoothness

  2019cites this paper
• An Improved Analysis of Local Search for Max-Sum Diversification

  2019cites this paper
• Chapter 2 Centralized Submodular Optimization

  2019cites this paper
• Generalized Budgeted Submodular Set Function Maximization

  2018cites this paper
• Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid

  2018cites this paper
• Online submodular maximization: beating 1/2 made simple

  2018cites this paper
• Resilient Assignment Using Redundant Robots on Transport Networks with Uncertain Travel Time

  2018cites this paper
• Soft Cache Hits: Improving Performance Through Recommendation and Delivery of Related Content

  2018cites this paper
• Online Submodular Maximization: Beating 1/2 Made Simple

  2018cites this paper
• Parallelizing greedy for submodular set function maximization in matroids and beyond

  2018cites this paper
• Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint

  2018cites this paper
• Supermodular Optimization for Redundant Robot Assignment under Travel-Time Uncertainty

  2018cites this paper
• 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, UK, August 27-31, 2018

  2018cites this paper
• Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

  2018cites this paper
• A Randomized Greedy Algorithm for Near-Optimal Sensor Scheduling in Large-Scale Sensor Networks

  2017cites this paper
• Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint

  2017cites this paper
• Multi-Objective Maximization of Monotone Submodular Functions with Cardinality Constraint

  2017cites this paper
• Femto-Caching with Soft Cache Hits: Improving Performance with Related Content Recommendation

  2017cites this paper
• On maximizing a monotone k-submodular function subject to a matroid constraint

  2016cites this paper
• Centralized Submodular Optimization

  2016cites this paper
• Local Search for Max-Sum Diversification

  2016influential citation
• Approximation algorithms for geometric dispersion

  2016influential citation
• Deterministic Algorithms for Submodular Maximization Problems

  2015cites this paper
• On the complexity of information planning in Gaussian models

  2015cites this paper
• Distributed Utility Games with Coverage Welfare Functions

  2015cites this paper
• Streaming Algorithms for Submodular Function Maximization

  2015cites this paper
• Monotone k-Submodular Function Maximization with Size Constraints

  2015cites this paper
• Scalable and distributed submodular maximization with matroid constraints

  2015influential citation
• Theoretical guarantees and complexity reduction in information planning

  2015cites this paper
• Optimal approximation for submodular and supermodular optimization with bounded curvature

  2013influential citation
• Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint

  year unknowncites this paper
• Online Caching Networks with Adversarial Guarantees

  year unknowncites this paper