• 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 SCIE

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 - epsilon). 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 - epsilon), a memory complexity O(K log K\epsilon) and query complexity O(log(2) K\epsilon) per element for the knapsack constraint K.

Keyword:

DR-submodular function Knapsack constraint Single-pass streaming Streaming algorithm Integer lattice

Author Community:

  • [ 1 ] [Tan, Jingjing]Weifang Univ, Sch Math & Informat Sci, Weifang 261061, Peoples R China
  • [ 2 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China
  • [ 3 ] [Zhang, Hongyang]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 4 ] [Zhang, Zhenning]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Source :

COMPUTERS & ELECTRICAL ENGINEERING

ISSN: 0045-7906

Year: 2022

Volume: 99

4 . 3

JCR@2022

4 . 3 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:46

JCR Journal Grade:2

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count: 2

SCOPUS Cited Count: 2

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 8

Affiliated Colleges:

Online/Total:389/10617714
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.