One-pass streaming algorithm for DR-submodular maximization with a knapsack constraint over the integer lattice. (April 2022)

• Record Type: Journal Article
• Authors: Tan, Jingjing; Zhang, Dongmei; Zhang, Hongyang; Zhang, Zhenning
• Is Part Of: Computers & electrical engineering. Volume 99(2022)
• Publication Date: 2022-04
• Subjects: Integer lattice -- Streaming algorithm -- Knapsack constraint -- DR-submodular function -- Single-pass streaming; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2022.107766
• Languages: English
• ISSNs: 0045-7906

Abstract

Abstract: Due to its broad applications, maximizing a diminishing return submodular function with a knapsack constraint has been extensively studied recently. In the paper, we mainly consider this problem on the integer lattice. Assuming the optimal value is known, we first design a one-pass algorithm and prove that its approximation ratio is ( 1 / 3 − ɛ ) . Observing the difficult of actually knowing the optimal value, we design a streaming algorithm with two passes, where in the first round we find the maximum value of the unit vector to estimate the range of the OPT. Furthermore, in order to improve the performance of the algorithm, we design an online algorithm called DynamicMRT to reduce the number of rounds, eventually achieving an approximation ratio ( 1 / 3 − ɛ ), a memory complexity O ( K log K ∖ ε ) and query complexity O ( log 2 K ∖ ε ) per element for the knapsack constraint K . Graphical abstract: Highlights: Maximizing a diminishing return submodular function over the integer lattice. Design streaming algorithm for diminishing return submodular maximization. Space complexity is related to the knapsack constraint. The query number of per-element is related to the knapsack constraint.