Submodular Approximation: Sampling-based Algorithms and Lower Bounds

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 radic(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.

Authors

• Zoya Svitkina
• Lisa Fleischer

Keywords

• Approximation algorithms
• Computer science
• Load management
• Processor scheduling
• Polynomials
• Educational institutions
• Application software
• Lower Bound
• Sampling-based Algorithms
• Objective Function
• Class Of Problems
• Simple Function
• Load Balancing
• Value Function
• Estimation Algorithm
• Set Of Elements
• Approximate Solution
• Simple Algorithm
• Random Set
• Interesting Problem
• Decision Problem
• Algorithm Running
• Weight Of Elements
• Collection Size
• Knapsack Problem