A $(k+3)/2$-approximation algorithm for monotone submodular maximization over a $k$-exchange system

Abstract

We consider the problem of maximizing a monotone submodular function in a $k$-exchange system. These systems, introduced by Feldman et al., generalize the matroid k-parity problem in a wide class of matroids and capture many other combinatorial optimization problems. Feldman et al. show that a simple non-oblivious local search algorithm attains a $(k+1)/2$ approximation ratio for the problem of linear maximization in a $k$-exchange system. Here, we extend this approach to the case of monotone submodular objective functions. We give a deterministic, non-oblivious local search algorithm that attains an approximation ratio of $(k+3)/2$ for the problem of maximizing a monotone submodular function in a $k$-exchange system.

References in corpus (1)

• Non-monotone submodular maximization under matroid and knapsack constraints

Cited by in corpus (8)

• Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization
• Constrained Monotone Function Maximization and the Supermodular Degree
• A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
• Stochastic Monotone Submodular Maximization with Queries
• Algorithms to Approximate Column-Sparse Packing Problems
• The Maximum Traveling Salesman Problem with Submodular Rewards
• Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
• Almost Optimal Semi-streaming Maximization for k-Extendible Systems