  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.
