Indexed by:
Abstract:
In this paper, we provide a streaming algorithm for the problem of maximizing the sum of a supermodular function and a nonnegative monotone diminishing return submodular (MDR-submodular) function with a knapsack constraint on the integer lattice. Inspired by the SIEVE-STREAMING algorithm, we present a two-pass streaming algorithm by using the threshold technique. Then, we improve the two-pass streaming algorithm to one-pass and further reduce its space complexity. The proposed algorithms are proved to have polynomial time and space complexity, and a performance guarantee dependent on the curvature of the supermodular function. Finally, we carry out numerical experiments to verify the performance of the algorithm.
Keyword:
Reprint Author's Address:
Email:
Source :
JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN: 1382-6905
Year: 2023
Issue: 2
Volume: 45
1 . 0 0 0
JCR@2022
ESI Discipline: MATHEMATICS;
ESI HC Threshold:9
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 11
Affiliated Colleges: