4.6 Article

Approximating (m(B), m(P))-Monotone BP Maximization and Extensions

期刊

TSINGHUA SCIENCE AND TECHNOLOGY
卷 28, 期 5, 页码 906-915

出版社

TSINGHUA UNIV PRESS
DOI: 10.26599/TST.2022.9010033

关键词

submodular maximization; streaming model; threshold technique; approximation algorithm

向作者/读者索取更多资源

This paper discusses the optimization problem of maximizing the sum of suBmodular and suPermodular functions under a streaming fashion. It proposes a threshold-based streaming algorithm that achieves an approximation of ((1 - kappa)/(2 - kappa) - O(epsilon)) for BP maximization. The paper also considers a more general model with fair constraints and presents a greedy-based algorithm that obtains the same approximation.
The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular (BP) functions with partial monotonicity under a streaming fashion. In this model, elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions. The goal is to determine whether a subset from the stream of size bounded by parameter k subject to the summarized utility is as large as possible. In this work, a threshold-based streaming algorithm is presented for the BP maximization that attains a((1 - kappa)/(2 - kappa) - O(epsilon))-approximation with O(1/epsilon(4) log(3) (1/epsilon) log ((2 - kappa) k/ (1 - kappa)(2))) memory complexity, where kappa denotes the parameter of supermodularity ratio. We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation. We finally investigate this fair model under the streaming fashion and provide a ((1 - kappa)(4) / (2 - 2 kappa + kappa(2))(2) - O(epsilon))-approximation algorithm.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.6
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据