Indexed by:
Abstract:
The problem of submodular maximization on the integer lattice has attracted more and more attention due to its deeply applications in many areas. In this paper, we consider maximizing a non-negative monotone non-submodular function with knapsack constraint on massive data. We combine two proposed algorithms called StreamingKnapsack and BinarySearch for this problem by introducing the DR ratio gamma(d) and the weak DR ratio gamma(w) of the non-submodular objective function. Finally, we obtain the performance guarantee of the StreamingKnapsack supplemented by a simple one-pass algorithm, with the approximation ratio of the better output of them as min{gamma(2)(d)(1 - epsilon)/2(gamma d+1), 1 - 1/gamma(w)2(gamma d) - epsilon}. Meanwhile, both the time complexity and space complexity are dependent on the size of knapsack capacity K and epsilon is an element of (0, 1).
Keyword:
Reprint Author's Address:
Email:
Source :
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021
ISSN: 0302-9743
Year: 2021
Volume: 13135
Page: 364-373
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 7
Affiliated Colleges: