A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice
A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice
复制标题
DOI：
--
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Tasuku Soma;Yuichi Yoshida
中科院分区：
文献类型：
--
作者：
Tasuku Soma;Yuichi Yoshida
本文基于整数格上报酬递减性质的概念，考虑了次模覆盖问题的一个推广。我们的动机是机器学习中的真实的场景，这些场景不能被（传统的）子模块集函数捕获。我们证明了广义次模覆盖问题可以应用于各种问题，并设计了一个双准则近似算法。我们的算法是保证输出一个对数因子的近似解，满足所需的精度的约束。我们的算法的运行时间大约是O（nlog（nr）log r），其中n是基集的大小，r是坐标的最大值。对r的依赖性比朴素约简算法要好得多。在真实的数据集和人工数据集上的实验表明，该算法的解质量与朴素算法相当，而运行时间快了几个数量级。
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) sub-modular 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.