"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack
"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack
复制标题
DOI：
--
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Dmitrii Avdiukhin;G. Yaroslavtsev;Samson Zhou
中科院分区：
文献类型：
--
作者：
Dmitrii Avdiukhin;G. Yaroslavtsev;Samson Zhou
从大数据集中选取具有代表性的小规模摘要是机器学习、优化和数据科学的基石。受推荐系统和其他对海量数据的查询受限访问场景的应用的启发，我们提出了一个新的严格的算法框架，用于将该问题作为受线性(背包)约束的子模最大化问题的标准表述。我们的框架是基于用最好的附加项扩充所有部分贪婪解。它可以在任何计算模型中以可忽略的开销被实例化，从而允许实现经典的贪婪算法及其变体。我们在离线(贪婪+MAX)、多遍流(Sieve+MAX)和分布式(Distributed+Max)设置中给出了这样的实例。我们的算法给出了($1/2-\epsilon$)-近似，而大多数其他感兴趣的关键参数是接近最优的。我们的分析是基于一组新的一阶线性微分不等式及其稳健的近似形式。在典型数据集(电影推荐、影响力最大化)上的实验证实了通过我们的框架获得的解决方案的可扩展性和高质量。特定于实例的近似通常在0.6-0.7的范围内，甚至经常超过多项式时间算法的$(1-1/e)\约0.63$最坏情况的障碍。
The problem of selecting a small-size representative summary of a large dataset is a cornerstone of machine learning, optimization and data science. Motivated by applications to recommendation systems and other scenarios with query-limited access to vast amounts of data, we propose a new rigorous algorithmic framework for a standard formulation of this problem as a submodular maximization subject to a linear (knapsack) constraint. Our framework is based on augmenting all partial Greedy solutions with the best additional item. It can be instantiated with negligible overhead in any model of computation, which allows the classic \greedy algorithm and its variants to be implemented. We give such instantiations in the offline (Greedy+Max), multi-pass streaming (Sieve+Max) and distributed (Distributed+Max) settings. Our algorithms give ($1/2-\epsilon$)-approximation with most other key parameters of interest being near-optimal. Our analysis is based on a new set of first-order linear differential inequalities and their robust approximate versions. Experiments on typical datasets (movie recommendations, influence maximization) confirm scalability and high quality of solutions obtained via our framework. Instance-specific approximations are typically in the 0.6-0.7 range and frequently beat even the $(1-1/e) \approx 0.63$ worst-case barrier for polynomial-time algorithms.