Timezone: »

A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice
Tasuku Soma · Yuichi Yoshida

Wed Dec 09 04:00 PM -- 08:59 PM (PST) @ 210 C #86
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.

Author Information

Tasuku Soma (University of Tokyo)
Yuichi Yoshida (National Institute of Informatics and Preferred Infrastructure, Inc.)

More from the Same Authors