Submodular approximation: sampling-based algorithms and lower bounds

Details Submodular approximation: sampling-based algorithms and lower bounds Submodular approximation: sampling-based algorithms and lower bounds

2008-05-07

arxiv.org/abs/0805.1071v3

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Submodular approximation: sampling-based algorithms and lower bounds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Submodular approximation: sampling-based algorithms and lower bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Submodular approximation: sampling-based algorithms and lower bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-52197