A brief note on approximate optimization of submodular functions

2025/10/20 by Alen Alexanderian, Alexanderian, Alen
Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #math.OC

paper · pdf · doi:10.48550/arxiv.2510.17610

9 pages. Made minor revisions and further expanded the discussion of submodularity

arxiv created 2026/07/30 · arxiv updated 2026/07/31

Abstract

We review some basics from submodular function maximization. We also detail the greedy method and a couple of its more efficient variants for approximately maximizing monotone submodular functions.

Related

• Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization
• A Refined Analysis of Submodular Greedy
• Improved Approximation Algorithms for k-Submodular Function Maximization
• Constrained Submodular Maximization: Beyond 1/e
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions