Indexed by:
Abstract:
Submodular maximization is of great significance as it has included many classical combinatorial problems. In this paper, we consider the maximization of the sum of a supermodular function and a monotone DR-submodular function on the integer lattice. As our main contribution, we present a streaming algorithm under the assumption that the optimum is known, and a two-pass streaming algorithm in general case. The proposed algorithms are proved to have polynomial time and space complexity, and a performance guarantee dependent on the curvature of the supermodular function.
Keyword:
Reprint Author's Address:
Source :
COMPUTATIONAL DATA AND SOCIAL NETWORKS, CSONET 2021
Year: 2021
Volume: 13116
Page: 68-75
Cited Count:
WoS CC Cited Count: 1
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: