• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Tan, Jingjing (Tan, Jingjing.) | Zhang, Dongmei (Zhang, Dongmei.) | Zhang, Hongyang (Zhang, Hongyang.) | Zhang, Zhenning (Zhang, Zhenning.)

Indexed by:

EI Scopus

Abstract:

Maximization of non-negative monotone submodular set functions under a knapsack constraint have been extensively studied in the last decade. Here, we consider the streaming algorithms of this problem on the integer lattice, or on a multi-set equivalently. This is more realistic for many practical problems such as sensor location and influence maximization. It is well known that submodularity and diminishing return submodularity are not equivalent on the integer lattice. We mainly focus on maximizing the diminishing return submodular (DR-submodular) functions with knapsack constraint on the integer lattice. Finally, by utilizing the binary search algorithm as a subroutine, we design an online streaming algorithm called DynamicMRT. Furthermore, we prove that it is a (1 / 3 - Ε) -approximation algorithm with O(Klog K) memory complexity and O(log K) query complexity per element. © 2021, Springer Nature Singapore Pte Ltd.

Keyword:

Approximation algorithms Parallel architectures Combinatorial optimization

Author Community:

  • [ 1 ] [Tan, Jingjing]School of Mathematics and Information Science, Weifang University, Weifang; 261061, China
  • [ 2 ] [Zhang, Dongmei]School of Computer Science and Technology, Shandong Jianzhu University, Jinan; 250101, China
  • [ 3 ] [Zhang, Hongyang]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 4 ] [Zhang, Zhenning]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China

Reprint Author's Address:

  • [zhang, dongmei]school of computer science and technology, shandong jianzhu university, jinan; 250101, china

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 1865-0929

Year: 2021

Volume: 1362

Page: 58-67

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 3

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 10

Affiliated Colleges:

Online/Total:575/10638052
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.