Submodular approximation: sampling-based algorithms and lower bounds

Abstract

We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions. The new problems include submodular load balancing, which generalizes load balancing or minimum-makespan scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound. We establish upper and lower bounds for the approximability of these problems with a polynomial number of queries to a function-value oracle. The approximation guarantees for most of our algorithms are of the order of sqrt(n/ln n). We show that this is the inherent difficulty of the problems by proving matching lower bounds. We also give an improved lower bound for the problem of approximately learning a monotone submodular function. In addition, we present an algorithm for approximately learning submodular functions with special structure, whose guarantee is close to the lower bound. Although quite restrictive, the class of functions with this structure includes the ones that are used for lower bounds both by us and in previous work. This demonstrates that if there are significantly stronger lower bounds for this problem, they rely on more general submodular functions.

References in corpus (1)

• Non-monotone submodular maximization under matroid and knapsack constraints

Cited by in corpus (14)

• Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
• Non-monotone submodular maximization under matroid and knapsack constraints
• Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
• Fast Semidifferential-based Submodular Function Optimization
• Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
• Learning Valuation Functions
• Approximate Submodular Functions and Performance Guarantees
• Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions
• Submodular Function Maximization over Distributive and Integer Lattices
• A Unified Framework of Constrained Robust Submodular Optimization with Applications
• Efficient Submodular Function Maximization under Linear Packing Constraints
• Graph Cuts with Interacting Edge Costs - Examples, Approximations, and Algorithms
• Subadditive Load Balancing
• A Note on Optimizing the Ratio of Monotone Supermodular Functions