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

2014/01/01 by Yuval Filmus, Justin Ward · 95 citations
Computer Science · Mathematics · #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Function (biology) #Greedy algorithm #Mathematical optimization #Mathematics #Matroid #Monotone polygon #Optimization and Search Problems #Oracle #Rounding #Submodular set function

paper · doi:10.1137/130920277

published in SIAM Journal on Computing 43(2), 514-542 (Society for Industrial and Applied Mathematics)

openalex publication_date 2014/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/26

Abstract

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 curvature c, we adapt our algorithm to produce a (1-e^-c)/c approximation. This matches results of Vondrák [STOC, ACM, New York, 2008, pp. 67--74], who has shown that the continuous greedy algorithm produces a (1-e^-c)/c approximation when the objective function has curvature c with respect to the optimum, and proved that achieving any better approximation ratio is impossible in the value oracle model.

Citations

• An analysis of approximations for maximizing submodular set functions—I
• A threshold of ln n for approximating set cover

Cited by

• Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
• FPT-Algorithms for the ℓ-Matchoid Problem with a Coverage Objective
• Femto-Caching with Soft Cache Hits: Improving Performance through Recommendation and Delivery of Related Content
• Resilient Assignment Using Redundant Robots on Transport Networks with Uncertain Travel Time
• A Simple Bound for Resilient Submodular Maximization with Curvature
• Logarithmic Approximations for Fair k-Set Selection
• Planning with Submodular Objective Functions

Related

• A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
• Constrained Submodular Maximization via Greedy Local Search
• Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
• Optimal approximation for submodular and supermodular optimization with bounded curvature
• Fast Non-Monotone Submodular Maximisation Subject to a Matroid Constraint