This event has ended. View the official site or create your own event → Check it out
This event has ended. Create your own
View analytic
Wednesday, December 9 • 19:00 - 23:59
A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice

Sign up or log in to save this to your schedule and see who's attending!

We consider a generalization of the submodular cover problem based on the concept of diminishing return property on the integer lattice. We are motivated by real scenarios in machine learning that cannot be captured by (traditional) submodular set functions. We show that the generalized submodular cover problem can be applied to various problems and devise a bicriteria approximation algorithm. Our algorithm is guaranteed to output a log-factor approximate solution that satisfies the constraints with the desired accuracy. The running time of our algorithm is roughly $O(n\log (nr) \log{r})$, where $n$ is the size of the ground set and $r$ is the maximum value of a coordinate. The dependency on $r$ is exponentially better than the naive reduction algorithms. Several experiments on real and artificial datasets demonstrate that the solution quality of our algorithm is comparable to naive algorithms, while the running time is several orders of magnitude faster.

Wednesday December 9, 2015 19:00 - 23:59
210 C #86

Attendees (1)