TY - GEN
T1 - Streaming Algorithms for Maximizing DR-Submodular Functions with d-Knapsack Constraints
AU - Liu, Bin
AU - Chen, Zihan
AU - Du, Hongmin W.
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - The problem of maximizing submodular functions has received considerable attention in the last few years. However, most of the submodular functions are defined on set. But recently some progress has been made on the integer lattice. In this paper, we study streaming algorithms for the problem of maximizing DR-submodular functions with d-knapsack constraints on the integer lattice. We first propose a one pass streaming algorithm that achieves a 1-θ1+d -approximation with O(log(dβ-1)βϵ) memory complexity and O(log(dβ-1)ϵlog‖b‖∞) update time per element, where θ= min (α+ ϵ, 0.5 + ϵ) and α, β are the upper and lower bounds for the cost of each item in the stream. Then we devise an improved streaming algorithm to reduce the memory complexity to O(dβϵ) with unchanged approximation ratio and query complexity. As far as we know, this is the first streaming algorithm on the integer lattice under this constraint.
AB - The problem of maximizing submodular functions has received considerable attention in the last few years. However, most of the submodular functions are defined on set. But recently some progress has been made on the integer lattice. In this paper, we study streaming algorithms for the problem of maximizing DR-submodular functions with d-knapsack constraints on the integer lattice. We first propose a one pass streaming algorithm that achieves a 1-θ1+d -approximation with O(log(dβ-1)βϵ) memory complexity and O(log(dβ-1)ϵlog‖b‖∞) update time per element, where θ= min (α+ ϵ, 0.5 + ϵ) and α, β are the upper and lower bounds for the cost of each item in the stream. Then we devise an improved streaming algorithm to reduce the memory complexity to O(dβϵ) with unchanged approximation ratio and query complexity. As far as we know, this is the first streaming algorithm on the integer lattice under this constraint.
KW - d-Knapsack constraints
KW - DR-submodular maximization
KW - Integer lattice
KW - Streaming algorithm
UR - https://www.scopus.com/pages/publications/85122022825
UR - https://www.scopus.com/pages/publications/85122022825#tab=citedBy
U2 - 10.1007/978-3-030-93176-6_14
DO - 10.1007/978-3-030-93176-6_14
M3 - Conference contribution
AN - SCOPUS:85122022825
SN - 9783030931759
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 159
EP - 169
BT - Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings
A2 - Wu, Weili
A2 - Du, Hongwei
PB - Springer Science and Business Media Deutschland GmbH
T2 - 15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021
Y2 - 20 December 2021 through 22 December 2021
ER -